Shift Before You Learn: Enabling Low-Rank Representations in Reinforcement Learning
Authors: Bastien Dubail
Stefan Stojanovic
Alexandre Proutiere
Venue: NeurIPS 2025 spotlight ()
Keywords: Low-rank representation
RL
successor measure
local mixing
Primary area: reinforcement_learning
TL;DR: The paper studies the estimation of successor measures in RL and low-rank assumptions

Abstract: Low-rank structure is a common implicit assumption in many modern reinforcement learning (RL) algorithms. For instance, reward-free and goal-conditioned RL methods often presume that the successor measure admits a low-rank representation. In this work, we challenge this assumption by first remarking that the successor measure itself is not approximately low-rank. Instead, we demonstrate that a low-rank structure naturally emerges in the shifted successor measure, which captures the system dynamics after bypassing a few initial transitions. We provide finite-sample performance guarantees for the entry-wise estimation of a low-rank approximation of the shifted successor measure from sampled entries. Our analysis reveals that both the approximation and estimation errors are primarily governed by a newly introduced quantitity: the spectral recoverability of the corresponding matrix. To bound this parameter, we derive a new class of functional inequalities for Markov chains that we call Type II Poincaré inequalities and from which we can quantify the amount of shift needed for effective low-rank approximation and estimation. This analysis shows in particular that the required shift depends on decay of the high-order singular values of the shifted successor measure and is hence typically small in practice. Additionally, we establish a connection between the necessary shift and the local mixing properties of the underlying dynamical system, which provides a natural way of selecting the shift. Finally, we validate our theoretical findings with experiments, and demonstrate that shifting the successor measure indeed leads to improved performance in goal-conditioned RL.

Shift Before You Learn: Enabling Low-Rank Representations in Reinforcement Learning
Bastien Dubail
Stefan Stojanovic KTH, Stockholm, Sweden stesto@kth.se
KTH, Stockholm, Sweden bastdubākth.ss se
Alexandre Proutiere
KTH, Digital Futures, Stockholm, Sweden alepro0kth. se
Abstract
Low-rank structure is common implicit assumption in many modern reinforce- ment learning (RI.) algorithms. For instance, reward-free and goal-conditioned RL methods often presume that the successor measure admits low-rank repre- sentation. In this work, we challenge this assumption by first remarking that the successor measure itself is not approximately low-rank. Instead, we demonstrate that a low-rank structure naturally emerges in the shifted successor measure, which captures the system dynamics after bypassing few initial transitions. We provide finite-sample performance guarantees for the entry-wise estimation of a low-rank approximation of the shifted successor measure from sampled entries. Our analysis reveals that both the approximation and estimation errors are primarily governed by newly introduced quantitity: the spectral recoverability of the corresponding matrix. To bound this parameter, we derive new class of functional inequalities for Markov chains that we call Type II Poincaré inequalities and from which we can quantify the amount of shift needed for effective low-rank approximation and estimation. This analysis shows particular that the required shift depends on decay of the high-order singular values of the shifted successor measure and is hence typically small in practice. Additionally, we establish a connection between the necessary shift and the local mixing properties of the underlying dynamical system, which provides a natural way of selecting the shift. Finally, we validate our theoretical findings with experiments, and demonstrate that shifting the successor measure indeed leads improved performance in goal-conditioned RI.
Introduction
In reinforcement learning (RL). the complexity of environment dynamics requires structural as- sumptions to achieve statistical efficiency. A widely adopted approach assumes that key quantities admit low-dimensional feature representations, effectively imposing low-rank structure on matrices underlying various RL components such as the Q-function
(57
55 60), transition kernel (2) 33 59))
graph Laplacian (46
c4 and successor representation (15 58 Some works even aim to learn
universal low-dimensional representations transferable across tasks, as in -Brak--d models (62) (3) and goal- condiiioii RL (3) (1).. Despite their empirical success and emerging theoretical analyses, fundamental questions remain:
Why should low-rank structure arise in MDPs, and under what conditions does yield accurate, learnable representations?
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To address these questions, we examine how the long-term dynamics of an MDP naturally give rise to global structure that can be captured effectively particular, we
1.00
expected reward
through low-rank approximations. demonstrate that simple temporal shift of the succes- sor measure can substantially improve its alignment with low-rank structure. This shift reweights transi- tions to emphasize long-term behavior, filtering out short-term noise and amplifying the structural signal present in the dynamics. Crucially, its effectiveness hinges on the mixing properties of the underlying Markov chain, which determine how rapidly the pro- cess forgets its initial conditions and reveals coherent global patterns. Our main contributions are:
50
3.75
0.30
8
10
12
shift
Figure 1: The discrete Medium PointMaze environment (see Section [6). Performance of goal-conditioned RL based on the rank-r approximation of the k-shifted successor mea- sure. Peak performance occurs non-zero shift, suggesting that shifting the successor measure can improve policy learning under low-rank constraints.
(a) We introduce the notion of spectral recoverabil- ity (Definition B to quantify the approximation error incurred by low-rank representations. We show that standard successor measures lack spectral recover- ability (Proposition D motivating the use of shifted successor measures which discard initial transitions and emphasize long-tenm ang-term dynamics. We prove that sufficiently large shifts guarantee spectral recoverability (Section S).
(b) We provide finite- sample performance guarantees for the entry-wise estimation of a low-rank approximation of the shifted successor measure from sampled entries (Thm. D Our analysis reveals that the estimation error is also governed by the spectral recoverability of the shifted successor measure.
(c) To characterize when spectral recoverability holds, we introduce a novel class of functional in- equalities for Markov chains, which we call Type II Poincaré inequalities (Thm. 2 These inequalities allow to quantify the amount of shift required for effective low-rank approximation and estimation. Moreover, we relate the required shift to the local mixing properties of the underlying dynamical system. These properties measure the extent to which the state space admits a decomposition into subsets within which the local dynamics mix rapidly.
(d) Finally, we validate our theoretical insights through experiments on learning the shifted universal successor measure in goal-conditioned RL. This representation enables the simultaneous learning of optimal policies for reaching a variety of goals. representative result is shown in Figure
2 Related Work
Low-rank approximations in RL. Low-rank models are ubiquitous in reinforcement learning. These models rely on low-rank approximations of certain matrices: most notably the Laplacian (46
63), the latter often considered better candidate for low-rank modeling (63). While these models are empirically effective and supported by intuitive heuristics based on spectral properties (see e.g. (38), they often
35 and the successor representation [5
58 36
lack rigorous theoretical justification. Our work aims to address this gap by establishing a connection between low-rank structures and the mixing behavior of the underlying dynamics.
Sample complexity bounds. Numerous studies have established performance guarantees for estimating low-rank structures reinforcement learning (RL). Several approaches draw inspiration from matrix completion techniques and have been applied, for example, to the estimation of the Q-function (57) 55 63 60). Our work is closer to the low-rank/linear Markov Decision Process (MDP) framework explored in (66) 2 68 69 59), where the transition kernel is modeled as bilinear factorization of the form P(s, a, s') = (s,a) o(s'). A special case arises when the factors are constrained to be non- negativee,, yielding models such as (soft) state aggregation and block MDPs
19 56 68 28 To the best of our knowledge, we are the first to analyze the sample complexity of estimating successor measures. Importantly, since successor representations are typically full-rank, imposing a striet low-rank assumption would be inappropriate. Alternative notions of rank have been proposed in the function approximation setting (30 61 18 32); however these depend not only

---

the dynamics but also on the choice of the function class. In contrast, our analysis does not rely on function upproximation or any structural assumptions, and allows intrinsic structure emerge naturally from the mixing properties of the underlying dynamics.
Mixing phenomena. To bridge matrix estimation and dynamical behavior, introduce spectral recoverability, parameter that quantifies both the SVD truncation error and the difficulty of recov- cring matrix entries from partial observations. Our approach inspired by (II), who established minimax bounds for matrix completion under a bounded nuclear norm. In contrast, we focus on entrywise estimation, which requires consideration of singular vectors. Spectral recoverability thus blends classical notions of coherence and nuclear norm, enabling entrywise error analysis via the leave-one-our technique of ( On the other hand, connects to classical mixing measures in Markov chain theory and can thus be bounded by revisiting classical tools such as functional inequalities (77) and spectral analysis (22). However, unlike traditional approaches that focus on global mixing times, our focus is on statistical estimation for which local and thereby weaker notions of mixing may suffice. This geometric intuition shares conceptual similarities with the works of (45) (9) on decomposable Markov chains and of (39) on spectral partitioning of graphs via eigenvectors of the adjacency matrix, which thus also connect with the block Markov chains mentioned previously.
3 Preliminaries
3.1 MDPs and shifted successor measures
Consider Markov Decision Process (MDP) with finite state space S and action space A == Use As. where A, denotes the set of actions available in state s. Define the set of state-action pairs as X Use (s} As, and let n denote its cardinality. We write element of X. The dynamics of the MDP are governed by transition matrix P E R-Yx5 where P(s, a.,& a') represents the probability of transitioning to state s' when taking action a in state 8. policy is defined as a stochastic matrix π e SKA, where Tssa)) denotes the probability of selecting action in state The policy ı induces Markov chain over X' with transition matrix Pz. defined as: P~ ((s, a), , (s', a²))= P(s, a, s') s')xx''', a'). The MDP is completed by specifying reward function R : X - RR When the state-action pair (s,a) is visited at time step 2 reward of R(s,0) a) is received. Given a discount factor 7 E (0, 1) the performance of policy i is characterized by its Q-function: ((R.T) (s, a) = E Ei 7 R(5T az) {
(s.0) to denote a generic
(sō, "ī) (. where (s):
(sf.a)) az)) is the state-action pair visited under at time t, through its value function EaSd, ((5,a))((R.)) (s.aa.
The Q-function can be expressed as a matrix-vector product. To make this explicit, define the successor Xx*" Then Q(R.a) (s. E100 7 ppp R(s,(s = Ma R(s. a). aa Mr((s,a)
measure as M₂ == (I (1-7Pa)*
d')) ,a). This formulation separates the dynamics from the rewards, showing that evaluating a policy for any reward function reduces to computing M2 (15 63). The problem of estimating the successor measure is referred to as reward-free policy evaluation. For this problem. we would like to obtain guarantees w.r.t the || |l=,, norm defined as lo, == sup feR x1l 11_ ||Af Indeed, suppose that we have an estimate M2 of Mn, and hence an estimate @R..)) = M, of the Q-function. This in turn allows us to improve the policy by acting greedily with respect to @)(..a), However, for this procedure to be reliable, we require entry-wise control over the error in @(R.a), which can be guaranteed by bounding the eиror in M, in the || loc, norm: [ = M - M2 R
where we use matrix product notation: M,
[R] As we show later in the paper, obtaining accurate estimates of M,, can be statistically challenging. The objective of this paper is to explain why shifting the successor measure may address this challenge.
AM7--M,
Definition (k-shifted successor measure). Let t 2 O. The k-shifted successor measure is defined as Mr := :::::=p>< 7 -
The k-shifted successor measure Mr,k captures the dynamics of policy starting from time step k onward. It allows us to quantify the cumulative discounted reward collected under v after the first steps. For any reward function R, it satisfies: MR, a) Σizo y pt*k a))
3

---

3.2 Measure-induced norms and SVD
To analyze the accuracy of estimators of the (shifted) successor measure w.r.t the || oa norm and make the link with mixing phenomena, we will use measure- measure-induced induced norms and SVD (refer to Appendix A. for a detailed description). Consider probability measure on X' whose support is X For J.9 e Tæ define the v-scalar product as (f := Enex
so that (TR (.:)))) y is a Hilbert space. We define for all f R M R-Xx the v-induced norms as: for any P, E [0,
Ifller>>> = (2)(x()) 1/P maxxax [[(x]
|M f fla(w)) feRA: foo Il llflee
if <00000000000000000
sup
p= :
For simplicity, we keep the measure implicit and use the notation 1/lpp (Illerro>) and |M [M (r(e)))) Note that I does not depend v. We will be mostly interested in the spectral
norm ||M 1.22 and the two-infinity norm |2 as we always have //00.0 & 12,00 Using
v, we can define the notions of adjoint of a vector f and of a matrix M: f*(x) (xx) (() and
M (z. v(x)M( This allows us to revise the notion of singular value decomposition by
v(y)
replacing the usual transpose operator with the adjoint.
Definition 2 (v-SVD). The v-SVD of the matrix M R takes the form M UVVI where E (o:) is a diagonal matrix made of non-negative values that we always assume to be in non-increasing order: 01 2 22 2 ..., while U, V e Raxx are unitary the sense UT UU = and VVV VV The v-SVD can be expressed as M Σx_ dyy; where the left and right singular vectors (v%)): (o:); form orthonormal bases (16) thy 1 and v Mb 0 for i # j). The entries (z).
of U, V are then Uxx, i) (o()),
Given 2 O. we write [M], U,E,, V for the v-SVD truncated to rank and [M],, M M-[M]-- We finally note that the usual SVD corresponds to the case where is uniform, up to a normalizing factor n. In what follows, to simplify, the D-SVD is referred to as the SVD.
3.3 Spectral recoverability
Our goal estimate the (shifted) successor measure with entry-wise guarantees by approximating the corresponding matrix via an estimate of its truncated SVD. Truncated SVD is a well-established technique for matrix approximation when considering the Frobenius or nuclear norm. By the Youkrt-YYung--iirkky theorem, for a matrix M R=*,,, its rank-r truncated SVD [M], provides the optimal rank-r approximation with respect to the Frobenius norm, with error [[M]> 1 Σn Ei of entirely determined by the spectral tail. When estimating the matrix from samples of its entries, the entry-wise error often depends on the coherence of the top T singular vectors. Coherence measures how concentrated or spread out the singular vectors are with respect to the standard basis. High coherence implies that a few entries dominate, making estimation from partial observations harder, while low coherence suggests that all entries are comparably informative. For detailed discussions, see, e.g., & 53 48). In our setting, we adopt a similar notion of coherence. For the top left singular vectors (1:) of M, we define the coherence as: c c((w))))) := 111,,,11,.. max
1 7 Σm (z)
When we seek guarantees in entry-wise norms such as 1. 12.00 or || 1o,,,0 it is not clear whether the truncated SVD [M], still yields a meaningful approximation of M. It is also not obvious what quantity governs the estimation error when attempting to recover [M]] from sampled entries. To address these questions, we introduce the concept of spectral (ir)recoveaability. which serves as a suitable quantity for controlling the approximation and estimation errors when the || 12,00 or I 20,00
norms are considered.
Definition 3 (Spectral (ir)recoverability)) Let M E Rxn and let M = Σ. a3too! be its SVD. The spectral irreovvrrbiliity of M is {(M) := max E (x)) The spectral recoverability is <(M)-1.
The spectral irrecoverability of a matrix M can be interpreted as a nuclear norm weighted by the left singular vectors of M, and it quantifies both the low-rank structure and coherence of the matrix. As
We discuss extensions where this is not the case in Appendix C

---

stated in the following lemma, proved in Appendix A the low-rank approximation error of M in the I 1, or bc.00 norm is controlled by E(M).
Lemma 1. Let e R We have: for any 1 1 < n, |M [,, Vor+i
This lemma serves as an analogue, under the ||||2,00 norm, of the "key lemma" from ①I (specifically, Lemma 3.5), which underpins a universal thresholding SVD procedure in the Frobenius norm setting. In our context, the lemma implies that | [MM][]]rll2... S for the largest rank such that o, 2 2 This provides principled criterion for selecting the rank in truncated SVD when targeting an accuracy level in the |2.00 norm. Additionally, for the problem of estimating the matrix from sample entries with 12,,, guarantees, we derive sample complex- ity lower bound scaling as E(M), see Appendix
I[Masb-lll..
25
50
v Vori McN)
75
0
6
shift &
Figure 2: Approximation error as function of the shift parameter it and rank r. The theoretical upper bound serves as a first-order proxy for the entry- wise error. We use the standard 12- norm, which matches (up to /n factor) the variant from Section 3.2 under the uniform measure и. See Section for experimental details.
We conclude with few remarks. and || are closely related as | max, Σ, (/
E(M)
(.)(M). When M has rank r, the spectral irrecoverability satisfies: 5(M) & 01 |1r|2,_ connects {(M) to classical notions of coher-
rojd(( which
ence. Finally, as shown in Fig. 2 the low-rank approximation error the shifted successor measure improves when the shift k increases (see Section 5 for theoretical justifications).
4 Estimation of the Shifted Successor Measure
4.1 Main result
We assume access to a dataset of transitions as,a, s') collected offline. Let Z.,a denote the number of independent transitions observed from the state-action pair (s, a). Our analysis provides estimation error bounds conditional on these counts, we may treat the Z.o. as deterministic. Using the then also form (=,(s.)) a). ), (s), ('),, (s',saa)) ,a) as the empirical estimator of Pµ. We can then build a simple estimator of the k-shifted successor measure Mr,k P (1 ~P=)) by taking MG = Ph - -Pa)-
data, form the empirical estimator P(s,a,,')= Ys,,,'/ / and given policy a,
Our final estimator of Mr obtained by computing the truncated =-SV [M of M We derive guarantees for this estimator under any probability measure of the following form. Let be a probability measure on S; we define y such that v(s, a) = u(s) a) for all (s, a). In the following theorem, d, denotes the i-th singular value of Mr.x in the D-SVD, and Ux,inv denotes the invariant measure of the Markov chain P.. We also define for (0,
v(s,a) Zeou(s' log(rn/6),
T == max (k: (1 -2)-
max (s'
σ1 max
|| 12,,0 :
M 7.
2,00
dv
du dV>
Essti ==
Ts:
(2)
or(or 0r+1)
dv
du
Expprox = (or+1((MM.))
(3)
Theorem 1. There is universal constant C O such that for any k 0, any probability measure on X. any 1 1 r n, and all 5e 10, we have, T $ 1, with probability at least 1 1,
M +]r Mn. 2.00 @ S CEestim + Eapprox
(4)
5

---

In the proof presented in Appendix C the estimation and approximation errors, respectively: [[ [M Cestim and [[ M 2,00 & Eupprox-
we show that Ceettim and Expprox are upper bounds on
4.2 Discussion
We discuss the terms involved in the estimation error upper bound below.
(a) The term A 21 max([ MM, (Mla........ 7. .l..)) comes from the so-called leave-one-out analysis, a
or(0)-0,=1)
step in the proof that aims at going from error bounds in spectral norm error bounds in || 11-12, The numerator can be controlled via the spectral recoverability of Mr. since |Mr,* S (1E(M==,)) For A to be controlled, that σ /a, is bounded and the gap σ, rr+ is significant. In Appendix C or Or+1 in case of bounded spectral irrecoverability.
hence need to control the spectral recoverability of M to have such we discuss how to control
(b) The term B = d(v, Vnr,nn) == de
involves the Radon-Nikodym derivative of
da
w.r.t. inv and V/ inv w.r.t. v. It captures the discrepancy between used to compute the SVD, and the invariant measure inv of the Markov chain under policy æ. The choice of is under the control of the practitioner. In practice, it may correspond to the empirical distribution of the dataset or chosen arbitrarily, for example, as the uniform distribution, in which case the SVD reduces to the standard SVD. On the other hand, the invariant distribution V iiv is more naturally aligned with the dynamics and yields the tightest possible bound. Setting v = Vn,innv eliminates the multiplicative factor B, resulting in the best-case guarantee. However, estimating Vrjiuv exactly may not necessarily be feasible. Theorem accommodates potential mismatch between v and Fr,invv showing that is sufficient for approximate the invariant measure up to constant factor.
(c) The term C = max (k, (1 ?))) comes from extending the concentration results in spectral norm of P to the shifted successor measure Mr The form of this term critically relies on comparison of v with the invariant measure, allowing us to exploit contraction properties and avoid exponential dependence in i ( (1-7)-1
(d) The D max(s, (s) (=)x)))XX (,,a((s(aa)) log(rn/6) can eventually be traced back to the
v(s.a)
concentration in spectral norm of the empirical estimator P. and is the only term that depends on the number of observations: if we want & small this factor shows how large each Z,,a should. Because of the ratio v( v(*,a) the result applies primarily to the case where exhibits some kind of homogeneity. "()',a')'
Corollary 1. Assume that {(Ma,k), 01/0,, (ax
v(st.a') and d(v, Un,inv) are O(1),
v(s.0)
and that Tr+1 22(1). Then a sufficient condition for [[M [Mr = O()) with probability at least - 8 is that the number of observations per state-action pair satisfies mill),a) Za,a O log(nr/6))
From the above result, we deduce that under the structural assumptions made on M A. the sample complexity to obtain an estimation error scaling as s in the 12.00 norm scales as n/e² up to the logarithmic term. Without structure, this sample complexity would necessarily scale as n²/=². We provide more detailed discussion about these assumptions, including the role of the measure v, the rank, etc. Appendix C
When Low-rank Structure Emerges: Local Mixing Phenomena
There is no reason to expect the transition kernel P (or Pa) to exhibit low-rank structure, and in view of the following proposition (proved Appendix the same observation holds for the successor measure.
Proposition 1. Let Pa Buxn, For all y (0,1), 0, ie [n], Consequently 1.M Toy
((P)) Itx s <a;(M,))) s (.(Pt)
--7
yn
and MM,,,ll,, I0y
1e

---

However, the situation changes when we consider powers of the transition matrix: for some k 1, the matrix Pk may become approximately low-rank. Specifically, if the Markov chain is ergodic. then P approaches a rank-I matrix nears the mixing time. This observation suggests that the k-shifted successor measure =, may also exhibit low-rank structure for high values of k. However, the mixing time can be prohibitively long, and applying such a large shift would be impractical. This raises natural question: can a low-rank structure emerge at smaller values of k, before the chain has fully mixed? We address this question by developing theoretical tools determine from which value of k the 22. norm and the spectral irreoverabilityy of Ma, become bounded. We relate this threshold to a concept we refer to as local mixing of the underlying Markov chain.
For notational convenience, throughout this section, we write P (resp. M2) in place of Pa (resp. Ms.k).. We also define Vmin := mingex (=) We observe that |M& 2,00 |[ 00
22,00 o0lls...l/P/ ||
- (--7)-1pp P1Pp 12, and hence in what follows we restrict our attention upper bounding | 2,.00
We discuss how to perform a similar analysis for [MM 2,000 and {(M&)) Appendix G
5.1 Local mixing estimates via Poincaré inequalities
To estimate the smallest value of k for which | | ||2,00 becomes bounded, we develop and leverage functional inequalities inspired by those used analyze the mixing times of Markov chains (see, e.g.. (49 54)). Appendix provides a detailed introduction to these techniques, as well as the proofs of G
all the results of this section. We introduce the Dirichlet form Epp, (f.9) = ((T ((T-PPi) PPtt)ss) :9), for all f. e R.. The next theorem shows that deriving functional inequalities on the Dirichlet form allows us to control p*] 2,.00
Theorem 2. Suppose there exist X, C O such that P satisfies the type 18 Poincaré inequality
V 211fl2 s ff
(5)
Then for all k 0:
1 2,00 S (umin - (1 CC
When p is the invariant measure of P. the Courant-Fischer theorem (Theorem 3.1.2 in (27 yields (5) with 1 (P) and C 1, which in turn leads to bound on the mixing time that depends on the singular gap of P. However, as we show below, type II inequalities can also be derived using higher-order singular values of P. This leads to significantly faster exponential decay rates for | 22. albeit at the cost of a larger limiting constant C. Interestingly, our analysis reveals connection between this limiting constant and the coherence of the singular vectors.
Theorem 3. Suppose the underlying measure v is the invariant measure of P. Let P UEV' be the SVD of P. and 01 2... 2 on 2 be the corresponding to singular values. (a) For all r e [n]. for all function f e R", we have
1- o
1 s E (1-o;, 11517
(6)
2
(b) For all e [n]. the result of Theorem holds with X = (1 o/+1)/2 and C = 2|1,,1
As consequence, if the coherence -- IU, 12,00 of the first left singular vectors of P is known to be bounded by C/2 (independent of n)). then we can suggest to apply shift k log( (or(Cn) / log((1 122) to ensure that |2 O(1) and that M₁ can be estimated efficiently by using a low-rank approximation. Such a shift & is typically much smaller than the mixing time (when d2 is close to I while ar+1 remains bounded away from it). Note however that the singular values and the coherence of the singular vectors of P may be unknown in practice. In such cases, we propose an alternative method to study the decay rate of pkl| ||,000
5.2 Decomposable Markov chains
Another strategy to analyze the decay rate of || 12,00 is to study local mixing behavior of the Markov chain via type II Poincaré inequalities, and combine these inequalities to derive global type II Poincaré inequality. We formalize this idea as follows.
"This terminology is inspired by (54) Chapter 2), where the author distinguishes two variants of Nash's argument, the second giving direct bounds mixing times (see Theorem 2.3.4).
7

---

Definition 4 (Induced Markov chain). Given a Markov chain on [n]] with transition matrix P and subset s [n]. the induced chain on S is the Markov chain on S with transition matrix Ps given by
y I, P(x,))+ Ens P(x,2) y=
P(x,y)
Va,ye S: Ps(x,y)=
= ()
The induced measure V/s is the measure on S given by ps(x)= == ((=) for all I S. We also denote by (PP.( E(P))ss the Dirichlet form constructed with the scalar product (:-:)e-
Proposition 2. Let be Markov chain on [n] with invariant measure and [n]]. Suppose the induced chuins (PP)); ss (PP))ss s= both satisfy type II Poincaré inequality with respect to the induced measure: for E {5
VfER. AB (fllee))))) S En (f. XBCB Ifle
Then P satisfies: E E Alfleee s (.ppr xCIlfflew) with X = min(As, and Oge C= max (1(S), v(S))
This result shows how to combine local type II Poincaré inequalities. It can be applied inductively to consider more complex partitions of the state space, i.e., with more than two subsets. When comparing to Theorem 3 we note max; (S,) plays here a role analogous to the coherence. Proposition very general, and we illustrate its application through the following simple example.
The 4-room environment. Consider Markov chain whose transition graph G be par-
titioned into 4 rooms or connected subgraphs (G.)se[4], as shown in Fig. 3
G is obtained
by adding an edge between each pair (G,, 1- Consider the simple random walk at random). It is an irreducible reversible Markov chain with transition matrix P and stationary distribution v. The chain induced by p2 on G2 is also reversible with spectral gap X;- The latter allows us to upper bound the (local) mixing time of the chain Proposition yields an explicit bound on | 1,00 2.00 which in turn, thanks to reversibility, leads to a lower bound of the spectral recoverability of pk In summary, can state the following result, proved in Appendix
G (at each step moves neighbor in G uniformly
G.
G2
G; as X; log(Vmin)
C4
Gs
Figure 3: The four-room environment.
Theorem 4. For all ls O, we have:
12 10 I (min ((.)) + (1
minse[4] +(1-mnnş{()) v
Furthermore, suppose that min v(Ga 2 for some constant c > 0. Then for all & E (0, for all
2 max log(vi -1 22cc). | 1-ppp[ppp -PP*) SE.
The above theorem illustrates how we can decompose a Markov chain into sub-chains so as to understand the shift needed estimate the matrix efficiently using a low-rank matrix. Assume for example that the graphs G; are bounded-degree expanders (26). Then we have X O(1) and v is uniform up to (1) factor. The required shift, log(n), is much smaller than the mixing time of the chain on G, scaling as n ln). We give further details and examples in Appendix G
6 Numerical Experiments B
We now turn empirical validation of our theoretical findings. In the previous sections, we analyzed how shifting affects the estimation of successor measures and the emergence of low-rank structure. Here, we test the hypothesis that these structural changes translate into tangible differences in learned behavior. Since accurate successor measures yield uniformly accurate Q-value estimates, we expect the impact of shifting to reflected not only in the estimated Q-values, but more importantly, the resulting policies. One domain where the practical relevance of successor measures can be directly examined goal-conditioned reinforcement learning (GCRL) (3,9 21 (3), where the objective is to learn policies n, (als) that reach arbitrary goal states g E S. This setting provides natural testbed for our analysis, as the quality of estimated successor measures directly determines the accuracy of goal-conditioned value estimates and, consequently, the learned policies.
*Code available httttp:://gccab....////tttt/tttt htt.caaww.cccoeetttttt/////eeeee

---

Following (63) consider the goal-specific reward function (g P(s' =gls Recall that Mr,k- (T- and thus P(T -P=) E. P() Es (+,.,;,) As shown in Proposition of (2), the corresponding state-action value function can written as the marginalized successor measure: (s.
This implies that the optimal policy obtained by acting greedity with respect Σo (5,, (,. Our experiments follow the setup (0, where the critic learns (( for a goal-marginalized policy TD (als) fs & "g (pp(()) with pD(g) denoting the empirical distribution of goals in the dataset 'D. This setup reflects a common GCRL scenario, where the agent reuses past experience collected under different goals improve sample efficiency.
Σ. (=,
10
(c)
(+)
accursty
0.5
0.0
0.00
100
"9
10
1.0
1.0
relaxed accuracy
(d)
(1)
MaA)
10
(b)
0.5-
10
10-3
10-4
25
index
rank
number trajectories
I-shift
Figure 4: (a) Discrete Medium Pointmaze environment. Each state 8 is colored by max, ΣbeA k= (s, g. b), with y = 0.95, goal g marked by star, and actions follow uniform policy TD. Arrows indicate the greedy policy π T(slg) argmax,, Σ. Mr A=1 M=1 a, g. b). (b) Singular values of shifted successor measures. (c-d) Accuracy (probability of reaching a random goal) and relaxed accuracy (reaching its 2-neighborhood) as function of rank and shift for true successor measures. (e-f) Same (c- (c-d), but for successor measures learned via TD. (g- (g-h) Accuracy vs. number of trajectories of length H 100. Results are averaged over 100 random goals and 5 seeds.
We explore how low-rank approximation (via truncated SVD) and temporal shifting of successor measures affect the performance of goal-conditioned policies. We perform experiments in the Medium PointMaze environment with 104 discrete states and 4 actions (see Figure (a)). Additional numerical experiments are provided in Appendix [ In Figure (b), we observe that shifting successor measures sharpens the spectrum, accelerating singular value decay. To quantify goal- goal-reaching performance, we report:
(upper row) accuracy, the probability of reaching the exact goal from random initial state, and (lower row) relaxed accuracy, the probability of reaching any state within two steps the goal.
The relaxed accuracy reflects that, in many scenarios, reaching nearby state is practically sufficient. For evaluations, the policy acts greedily with respect to the corresponding successor measure matrix. Figure (c) shows that even when using oracle successor measure, introducing temporal shift improves performance, especially when combined with low-rank approximation. This benefit particularly notable when success is defined more flexibly, as shown in Figure (d). These results suggest that shifting enhances the expressiveness of successor measures while compensating for rank constraints.
To estimate successor measures from data, we apply Temporal Difference (TD))learning with TD- errors 1 St4A+1 9, a++k+1 b (0tt. Qttk+1, g.b).. -M (8t, ag.g. g. b). where (g. b) S A and (St, St+k+1. a(+k+1) are sampled from D. As shown in Figure 4 (e-f), larger shifts degrade performance when successor measures are learned via TD. This aligns with the intuition that estimating long-horizon dynamics is harder and introduces more error, particularly in low-data regimes. Finally, we assess how data efficiency depends on the shift parameter by fixing the rank to 40 and varying the number of samples in Figure (g-h). We find that moderate shift (k 3)

---

consistently yields the best performance, suggesting a trade- off: while shifting improves expressivity. its estimation must remain tractable. This is also illustrated in Fig. Iin $
The choice of rank and shift parameters. As shown in our results, the performance of policies derived from low-rank approximations improves substantially even for small rank values, consistent with prior findings (67) (7). In practice, we recommend selecting a rank much smaller than the state-space dimension. Note, however, that the optimal rank often depends on the chosen shift value, and the two parameters should thus be tuned jointly. Prior work for instance, HIQL (51) already treats the number of steps subgoal as an ievironment-specifin hyperparameter.
7 Limitations and Future Work
Our work leaves open many questions, especially the algorithmic implications of our theoretical findings. We highlight below the main limitations this paper.
Downstream optimization of policies. Our main result provides guarantees for estimating shifted successor measures under a fixed policy, effectively performing reward-free policy evaluation. How- ever the effective benefit for downstream policy optimization, once reward is given, remains unclear and is not addressed in this paper. In line with prior studies (63 37), our numerical experiments in Section show that considering policies that are greedy w.r.. Q-functions estimated under uniform or exploratory policies can perform well in practice. This motivates our focus on the evaluation problem, leaving the theoretical and practical understanding of such greedy policies, why and when they work, as an open direction for future research.
Dependence generative model. Theorem | makes the strong assumption of access to an i.i.d. dataset transitions. This assumption effectively sidesteps the challenges of exploration and the use of sampled trajectories, which we leave an important direction for future work.
Extension to continuous settings. Our work is restricted to tabular MDPs for simplicity. However, most ideas extend naturally to continuous spaces by replacing matrices with linear operators and measures 6 (3) Extending Theorem I Junder suitable smoothness assumptions, following (57 59 65.. is a promising direction.
Limitations the experimental results. Shifting removes local information, and for tasks such as goal reaching, where rewards are sparse and given only at the end, this has little impact achieving optimal performance. However, in more general settings, we expect that combining shifted successor measures with estimates of local transitions could further improve performance. Our numerical results illustrate the theoretical findings and consider low-rank approximations using SVD. It remains unclear whether alternative low-rank approximation methods would exhibit different behavior. In Appendix H..)] we discuss potential extensions to non-tabe non-tabular settings. An open question is how much of this phenomenon carries over to function approximation settings and how it can be leveraged effectively there.
8 Conclusion
In this work, we considered the problem of estimating shifted successor measures. Our main result established an upper bound on the sample complexity for simple estimator based on SVD truncation. Unlike previous work, we make no structural assumption on the matrix, showing that structure would generally emerge naturally from local mixing phenomena. This led us to introduce shifted successor measures, to better distinguish between small-range transitions, which remain inherently high-rank, and long-range transitions where mixing phenomena take place and give rise to an approximately low-rank structure. This was empirically confirmed. Our experiments show that shifted successor measures are better approximated by their low-rank SVDs than the non-shifted counterpart, and that the use of shifts can bring performance improvements in (goal-conditioned) RL. These two main contributions open up many possibilities. From a theoretical perspective, we believe that our approach could be used to assess the sample complexity of estimating universal representations like model of (22). On the more practical side, the idea of shifting surely requires a more complete empirical analysis to better understand its impact across diverse RL settings.
the
10

---

Acknowledgments
This research was supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, the Swedish Research Council (VR), and Digital Futures.
References
[1] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Ann. Statist., 1843):1452-1474, 2020.
doi: 1214/19-A0S1880
34 40
[2] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs. Advances Neural Infor- Curran Associates, Inc., 2020.
mation Processing Systems, volume 33, pages 20095-20100
[3] Marein Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
[4] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity reinforcement learning with a generative model. Mach. Learn., 91(3):325 349, 2013. URL: https://doi 11111/0.11100/1199--0-111111 1007/ 013-5368--11111---1
doi :10
34
[5] André Barreto, Will Dabney, Rémi Munos, Jonathan Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. Advances in neural information processing systems, 30, 2017.
[6] Léonard Blier, Corentin Tallec, and Yann Ollivier. Learning successor states and goal-dependent values: A mathematical viewpoint. CoRR, fts/22011.0112 2021. URL: httpp:: / org abtpab////1111122221
arXiv:2101.0712
10
[7] Pierre Bremaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues, volume 31 of Texts Applied Mathematics. Springer Nature, Cham, 2nd edition 2020 edition, 2020. 33
Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Found. Comput. Math., (6):717-772, December 2009.
[9] Elliot Chane-Sane, Cordelia Schmid, and Ivan Laptev. Goal-conditioned reinforcement learning with imagined subgoals. In International conference machine learning, pages 1430-1440.
PMLR, 2021. g
[10] Sourav Chatterjee. Stein's method for concentration incqualities. Probab. Theory Related Fields, 138(1-2):305-33 2007. 2007, doi : 10, 100110000000/00040000000003
30
43
[11] Sourav Chatterjee. Matrix estimation by universal singular value thresholding. Ann. Statist., 43(1):177-214, 2015. doi 10. 0et.:1...2224410 1114/14-4444112120
[12] Sourav Chatterjee. Spectral gap of nonreversible markov chains. arXiv 2310. 10876, to appear Ann. Appl. Prob., 2025. URL: https:t////::xiii org/ abs 2310
2tt////a./223..../ 10876
54
[13] Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma. Spectral methods for data science: A statistical perspective. Foundations and Trendss in Machine Learning, 566-86666-806,
2021.
URL: http::/dp/.:tt www.dxx..o....ooo org/ /
doi 10. 1001155//2000000779 40
41
[14] Pierre Collet, Server Martínez, and Jaime San Martín. Quasi-stationary distributions. Probability and Applications (New York). Springer, Heidelherg, 2013. Markov chains, diffusions and
dynamical systems. doi 10. 1007/978- 0-77883---2----- 03131-2
33

---

[15] Peter Dayan. Improving Generalization for Temporal Difference Learning: The Successor Repre- sentation. Neural Computatioon 5(4):613-624 624, 07 1993. art.i::ttps: mit edu/ neco/ aaccoarticle- htteeeddf///////// 02/55////13//1122//3 neco. 1993. w...6.4.............. w11.611...pp.. pdf,
doi 1r1:10..1622eec..
1999.5.4.00 613
[16] Diaconis and L. Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab., 6(3):695-750, 1996. doi : 1tw//2/aa/aaaee 21144///0o//10999822249 55
[17] Diaconis and L. Saloff-Coste. Nash inequalities for finite Markov chains. J. Theoret. Probab.,
9(2):49--511) 510, 1996. doi: : 10. 1007/BF02214660
55 56
57
[18] Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in RL. In Marina Meila and Tong Zhang, editors. Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2826 2836. PMLR, 2021. URL:http //proceedings. mlr, www.s/ressseee.ee
press/v139/ htt///1199//u/1 html 2
[19] Yaqi Duan, Tracy Ke, and Mengdi Wang. State aggregation learning from markov tran- sition data. In H. Wallach. H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL: http:ttt/poocceeeiiiiiii mwwpaiiiinnnnnnuuusppeee.e neurips httppppprffileepppee. 200///11e00000226633777444111112
pdf
[20] Benjamin Eysenbach, Soumith Udatha, Russ R Salakhutdinov, and Sergey Levine. Imitating past successes can be very suboptimal. Advances in Neural Information Processing Systems, 35:6047-6059, 2022.
[21] Benjamin Eysenbach, Tianjun Zhang, Sergey Levine, and Russ R Salakhutdinov. Contrastive learning as goal-conditioned reinforcement learning. Advances in Neural Information Process- ing Systems, 35:35603-35620 2022. 8 63
[22] James Allen Fill. Eigenvalue bounds on convergence to stationarity for nonreversible markov chains, with application to the exclusion process. The Annals of Applied Probubility, 1:62-87, 1991. doi: doi: 10. 11111///aa/117770555900
55
[23] Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219, 2020. 60
[24] Sharad Goel, Ravi Montenegro, and Prasad Tetali. Mixing time bounds via the spectral profile. Electron. J. Probab., 11:o. 1, 1-26, 2006. doi : 10. 1214/EJP v11-300 55
[25] Diego Gomez, Michael Bowling, and Marlos C. Machado. Proper laplacian representation learning. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL: httpp:://openreeview net/
forum?id=7gL.f(5522 2
[26] Shlomo Hoory. Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer: Math. Soc., 43:439-561. 2006. URL: http::tttt::rt www. ams ort.s/s.rbbbbullle wwwpoo/ggw...oooooo/er/r 43 04/ doi : 10.
0970-96-----1-8 8/home. html
[27] Roger A. Horn and Charles R. Johnson. Topics in matrix analysis Cambridge University Press, Cambridge, 1994. Corrected reprint of the 1991 original.
57
[28] Yassir Jedra, Junghyun Lee, Alexandre Proutiere, and Se- Young Yun. Nearly optimal latent state decoding in block mdps. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 2805-2904. PMLR, 25-27
Apr 2023. URL: httL::tttt://///0 htttps://proceeediggg mlr ppwps//20////// wewp//eeeeeee..... html 2
[29] Mark Jerrum, Jung-Bae Son, Prasad Tetali, and Eric Vigoda. Elementary bounds on Poincaré and log-Sobole Sobolev constants for decomposable Markov chains. Ann. Appl. Probab,, 1444)
2004. doi 10. 1214//105051104400000033 3
12

---

[30] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-leamable. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning. volume 70 of Proceedings of Machine Learning Research, pages 1704-1713, PMLR, 06-11 mlr
Aug 2017. URL: https::t//// ttttps://prrceeedinng www.mm.....ppe..emmmm prress/v00/js jingg html
[31] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free ex- ploration for reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Pro- ceedings of Machine Learning Research, pages 4870 4879. PMLR, 2020. URL: http:
//proceedings.. mlr. wttppp/e1e//innn//00v0 html
31
[32]
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Anmual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual. pages 13406-13418, 2021. URL:
[33] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2137-2143.
PMLR, 09-12 Jul 2020.
[34] F. P. Kelly, Reversibility and Stochastic Networks. Cambridge University Press, USA, 2011. 58
[35] Martin Klissarov and Marlos C. Machado. Deep laplacian- options for temporally- extended exploration. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara En- gelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Ma- chine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaïi, USA, volume 202 of Proceedings of Machine Learning Research, pages 17198-17217. PMLR, 2023. URL: httpss:/proceedings.nt
html 2
[36] Tejas D. Kulkarni, Ardavan Saeedi, Simanta Gautam, and Samuel J. Gershman. Deep successor reinforcement learning. CoRR. (ts//660.02396, 2016.
URL: /tttp://axxi......//////// http://wwwvvorrg///////// has//bb//111000
02396 1exiv:16666 02396
2
[37] Cassidy Laidlaw, Stuart Russell, and Anea Dragan. Bridging rl theory and practice with the effective horizon. Advances in Neural Information Processing Systems, 36, 2024. 10
[38] Charline Le Lan, Stephen Tu, Adam Oberman, Rishabh Agarwal, and Mare G. Bellemare. On the generalization of representations in reinforcement learning. In Gustau Camps- Valls,Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 4132-4157, PMLR, 28-30 Mar 2022. URL: https::/prroeeet
mlr. press//
html
[39] James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multi-way spectral partitioning and higher-order Cheeger inequalities. In ST P2-Prcceeding of the 2012 ACM Symposium on Theory of Computing, pages 1117-1130, ACM, New York, 2012. doi: : 10. 1145/2213977
2214078 3
[40] David A. Levin and Yuval Peres. Markov chains and mixing times. American Mathematical Society, Providence. RI, 2017. Second edition of MR2466937J, With contributions by Elizabeth L. Wilmer, With chapter on "Coupling from the past" by James G. Propp and David B. Wilson, doii 10. 1090 1090/mbk/ 107
[41] Marlos C. Machado, André Barreto, Doina Precup, and Michael Bowling. Temporal abstraction in reinforcement learning with the successor representation. J. Mach. Learn. Res., 24:80:1- 80:69, 2023. URL: https: sttps://jmlrr org/ wwtgg/aaers/aaee weteeers/vv/2111111 html 2
13

---

[42] Marlos C. Machado, Mare G. Bellemare, and Michael H. Bowling. A laplacian framework for op- tion discovery in reinforeement learning. Doina Precup and Yee Whye Teh, editors, Proceed- ings of the 34th International Conference on Machine Learning, ICMI. 2017, Sydney, NSW, Aus- tralia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 2295- 2304. PMLR, 2017. URL: http::/procceednng mlr. wwwpppreeeossaeeep
Treess/v70/maccadooll wttp://iiin.......ees/////////aa
html 2
[43] Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL: https //openreview.oo
[44] Lester Mackey, Michael Jordan, Richard Chen, Brendan Farrell, and Joel A. Tropp. Matrix concentration inequalities via the method of exchangeable pairs. Amn. Probab., 42(3):906 945, 2014. doi 10. 11014/13-APP99
43
[45] Neal Madras and Dana Randall. Markov chain decomposition convere rate analysis. Ann. Appl. Probab., 12(2):581-666, 2002. doi :::1:10.114444 2aaa:....21///aaa/000255555611
[46] Sridhar Mahadevan and Mauro Maggioni. Value function approximation with diffu- sion wavelets and laplacian eigenfunctions. In Y. Weiss, B. Schölkopf, and J. Platt, editors, Advances in Neural Information Processing Systems, volume 18. MIT Press, 2005. URL:
wtwp://ewdddinn.e.eeeeeeeeeeeeee newrips. cc/ cc/pp//pp//acccccccecccc pappr_rillesssssee////aaaaaaeeee filee/iell///eelle waapeeffflee//pper///// pttpp/pappre////eeeee 266060966660655552877662-----262
pdf
[47] Sridhar Mahadevan and Mauro Maggioni. Proto-value functions: A laplacian framework for learning representation and control in markov decision processes. Mach. Learn. Res.,
8:2169-2231, 2007. URL: hitpss//dl acm. orgg/0o//10.555//31443333 5555513144511888 1314570 doi
00.5555/13144490 1314570 2
[48] Mehryar Mohri and Ameet Talwalkar. Can matrix coherence be efficiently and accurately estimated? In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedingy of Machine Learning Research, pages 534-542, Fort Lauderdale, FL., USA, 11-13 Apr 2011. 1. PMLR. URL: https: ptttps:://proceedinng mlr. wttpppereesssaiiiie/e/ htmm
4
[49] Ravi Montenegro and Prasad Tetali. Mathemattcal aspects of mixing times in Markov chains. Found. Trends Theor. Comput. Sci., 1(3):237-3544 2005. doi : 10. 1011/4400000000
55
56
[50] Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hicrarchical reinforcement learning. Advances in neural information processing systems, 31, 2018. 63
[51] Seohong Park, Dibya Ghosh, Benjamin Eysenbach, and Sergey Levine. Hiql: Offline goal- conditioned rl with latent states as actions. Advances in Neural Information Processing Systems, 16:34866-34891, 2023.
10 63
[52] Daniel Paulin, Lester Mackey, and Joel A. Tropp. Deriving matrix concentration inequalities
from kernel couplings, 2013. arXiv: 1305. 0612 43 44
[53] Benjamin Recht. A simpler approach to matrix completion. 121ull):3413-3440 December 1.
J. Mach. Learn. Res.,
[54] Laurent Saloff-Coste.
Lectures on finite Markov chains. In Lectures on probability theory and statistics. Ecole d' de probabilités de Saint-Flour XXVI-1996. Lectures given at the Saint-Flour summer summer school of probability theory, August 19- -e-Seeemberr 4, 1996, pages 301-413.
Berlin: Springer, 1997.
56 59
[55] Tyler Sam, Yudong Chen, and Christina Lee Yu. Overcoming the long horizon barrier for sample-efficient reinforcement learning with latent low-rank structure. Proc. ACM Meas. Anal. Comput. Syst., 112):29:1129:66 2023, doi: 10. 1
14

---

[56] Jaron Sanders, Alexandre Proutière, and Se- Young Yun. Clustering block Markov chains. Ann.
Stat., (8(6))3488-35111 2020. URL: pure. tue http:////ee//eee///7777711222220
pdf
doi: 10. 1214/19-A0S1999
2 29
[57] Devavrat Shah, Dogyoon Song, Zhi Xu, and Yuzhe Yang. Sample efficient reinforcement learning via low-rank matrix estimation. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. URL: http::: cc/ ccc/appr//000 2020//2220////// hwtp//aahaaaaaeeeaa/eeaaa /2t1///2222222222291999910031113 h/tpp///e/////////22222222222220
neurips Abstract.
10
[58]
Kimberly L. Stachenfeld, Matthew M. Botvinick, and Samuel Gershman. Design principles of the hippocampal cognitive map. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference Neural Infor- mation Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada. pages 2528-25366 2014. URL: https::/procceedinnn neurips. hccppappr//014/./0 00776666c112366b4444774466666633 Abstract.htmr html
2
[59] Stefan Stojanovic, Yassir Jedra, and Alexandre Proutière. Spectral entry-wise ma- trix estimation for low-rank reinforcement learning. Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Informa- tion Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 feaper_files, files files/paper 2023//ashh html
Alice Oh, Tristan Naumann,
URL: http://paperss nips wwtpcper_ppppppeeeeeee 16, 2023, 2023.
[60] Stefan Stojanovic, Yassir Jedra, and Alexandre Proutiere. Model-free low-rank reinforce- ment learning via leveraged entry-wise matrix estimation. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 30886-30924, Curran Associates, Inc.,
2024. URL: https: http::::///ppoceeeeedee http://ooreediinnnnnnurrrp.....e www.ipe.cccccceeeooeeeee ccppppprrrcpppppr...p..pep hatp/ppppe____f_e wwtess/apper//24////11 (4171223eldddF4444366e2252226333 Confereecoo pdf
[61]
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 Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of PMLR, 2019. URL: http://proccediing
Machine Learning Research, pages mlr. www.prressvvve v99/ sun sww19a. h9mmllmmll
[62] Ahmed Touati and Yann Ollivier. Learning one representation to optimize all rewards. In Marc Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wort- man Vaughan, editors, Advances in Neurul Information Processing Systems 34: Annual Confer- ence Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 14, 2021, vir- tual, pages 13-23, 2021. URL: https: http::////oooeeeeeeeeeeeee neur ipsurips..... wwwppppp.cccppppee wwwpccpppppppeeeeeeceeecceeeeeee /eoperr/221///1 2021/hash/ 1335d617c122444fff9o0
Tww.:aa998-Abbtaaacceeee Abstract.
[63] Ahmed Touati, Jérémy Rapin, and Yann Ollivier. Does zero-shot reinforcement learning exist? In The Fleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net 2023. URL. https://openrreveew www.ee..eeeffruoeeeeeee
1d=MYEap Cc=MVE
10 63
[64] Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in RL: learning representations with efficient approximations. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL: https
2
[65] Xumei Xi, Christina Lee Yu, and Yudong Chen. Matrix estimation for offline reinforcement learning with low-rank structure. CoRR, abs/2305. 15621, 2023. URL: http::://p//o org/10 48550/
13650/arXiv. arxiv. 2305. 15621 arXiv: 15621 doi 1...0.8800011. ARXIV 2305 15621
2
10
15

---

[66] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6995-7004. PMLR, 2019, URL: http: http:://pooceeddngg/ee mlr press/ / / 1tm.gtml11..1.111
[67] Yuzhe Yang. Guo Zhang, Zhi Xu, and Dina Katabi. Hamesssing structures for value-based planning and reinforcement learning. In International Conference on Learning Representations, 2020. URL: https://openrevies .wtp://oruunddddrklltttttte
10
[68] Anru Zhang and Mengdi Wang. Spectral state compression of Markov processes. IEEE Trans.
Inf. Theory, 6665):3202-3231, 2020. doi: 10. 100::001109//00 1109//TT 2019. 2956737 28
[69] 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,
16

---

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

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Each our theoretical results is stated with the full set of assumptions, and complete proofs provided in the appendix. We have made every effort to ensure that the arguments are rigorous and correct to the best of our knowledge.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We have made every effort to fully disclose all information necessary to reproduce the main experimental results. Section 6 and Appendix HH provide detailed descriptions of the experimental setup, and all code required to run the experiments is included supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
18

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide all code as supplementary material ensure reproducibility. Full
descriptions of the experimental setup are included in Section o and Appendix H. to the best of our ability, allow faithful reproduction of the main results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //iips.c//pple wttpccpppppppppeeeeeeeeeeeeeeeee wwwpce/ggiesss//eee httaa//gguidees/edeSubbiisssss sonoooooocss for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: All relevant training and evaluation details are described in Section 6 and Appendix H In addition, we provide the full code supplementary material, which includes all configuration files and scripts needed to reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
19

---

Justification: All plots involving stochastic components include standard deviation shading indicate variability, We also clearly state in the text the number of random seeds and the amount of data over which results were averaged.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide detailed information about the computational resources used for our experiments, including hardware specifications, memory, and runtime, in Appendix H to ensure reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: To the best of our knowledge, the research presented in the paper fully conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
20

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairesss considerations (e.g., deploymeett of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
21

---

Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssiippssiiii thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
22

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
23

---

Contents
Introduction
2
Related Work
3
Preliminaries
MDPs and shifted successor measures
reasure-induces norms and SVD
3.3
Spectral recoverability
Estimation of the Shifted Successor Measure
Main result
4.
4.2
Discussion
5
When Low-rank Structure Emerges: Local Mixing Phenomena
5.1
Local mixing estimates via Poincaré inequalities
5.2
Decomposable Markov chains
6
Numerical Experiments
Limitations and Future Work
10
8
Conclusion
10
Measure-induced Norms and SVDs, Shifted Successor Measures and Spectral Recover-
ability
26
A.I Mcasure-induced norms and SVDs
26
A.2 Spectral recoverability: Proof of Lemma
27
Sample Complexity Lower bounds for
2,
Guarantees
28
B. I Block Markov chains
29
B. 2 Proof of Theorem
29
Discussion and proof of Theorem
33
Discussion
................................
Main steps of the proof of Theorem
................................
Proof of Theorem
36
Entry-wise guarantees: leave-one-out analysis
40
D.I Entry-wise guarantees for SVD estimation: proof of Theorem
40
D.2 Technical lemmas
40
D.3 Proof of Propositions and
Concentration in spectral norm for stochastic matrices
43

---

E.
Main concentration inequality
43
The method of exchangeable pairs
43
Exchangeable pairs for independent multinomial variables
E,4
Concentration of the empirical estimator
46
Extension to shifted successor measures and leave-one-out concentration
49
Contraction properties of the map P P=
49
F2
Extension to shitted successor measure: proof of Theorem
49
Leave-one-out concentration
51
Local mixing phenomena
54
G.1
Singular value bound: proof of Proposition
54
G.2
Spectral recoverability for chains with normal transition matrices ................................
Functional inequalities for Markov chains
55
G.4
Type Il Poincaré inequalities and applications
56
G.4.
Proofs of Theorems[2lande
56
G.4.2
Combining inequalities of induced chains
G.4.3
The 4-room examples: proof of Theorem
58
H
Further Numerical Experiments
60
The 4-room environment).
60
H.2
Additional Navigation Tasks
60
H.3
Non-uniform Data Collecting Policy
62
Model-Based Estimation of Shifted Successor Measures
62
H.5
Extension to the Non- Tabular Setting
63
25

---

A Measure-induced Norms and SVDs, Shifted Successor Measures and Spectral Recoverability
In this appendix we establish the formalism that is used throughout the paper. We start with general notation.
Notation Given integers m S n, we write [m, (m,,..,,7)) n2) and in particular [M] (I,.... ,....,,.... We write n A m == min(m (n, w). Vectors are seen as column vectors, measures are identified with row vectors. We write for the all-one vector, L, the the indicator vector at i. Thus we write ] for the matrix with only one non-zero entry at coordinate (i,j), equal to 1. We use the notation = for positive semi-definite inequalities, abbreviated as p.s.d.. We use the usual Landau notations Oc), ((), etc. for asymptotic analysis.
n).
A.1 Measure-induced norms and SVDs
Norms with respect to measure Given measure μ on [n]. let (fig), : Em(m) (())))))))). Note that up factor n, the usual inner product is recovered by taking the uniform measure for μ. Given e [1, oo], we define the 8 norm
Ifflerc)) = (Enex (Enex((z) ((())))))) maxxax [f(z)
if 00
if =0
For simplicity may keep the measure implicit and write only Ifll, 1I lef We employ the term "norm" although I-llp define norms only if p has full support. Generally speaking, lot of notions considered in the sequel may not be properly defined if fu does not have full support. Rather than always requiring the measure to have full support, we take the convention that the results become trivial when an object ill-defined because of the norm. In particular, we define pmin min, u(i) and consider that umin = +oo if does not have full support.
When considering rectangular IR we need to define two underlying measures μ, / on [m] and [n]. If m, we always take μ= The adjoint operator A E RRm is the unique operator that satisfies (Af,)). (J,A5g), for all f RT ,g RR. It is explicitely given by
Adjoint operator and SVD
Ai,j) ((1)A(i,))
(7)
p(i)
If n and μ is uniform, A' AT is nothing but the transpose of A. Thus every notion that could normally be defined with a transpose will be here considered with the adjoint instead.
This applies in particular to the singular value decomposition (SVD). The left singular vectors (1b)) resp. right singular vectors (o):
(d:):am nAm of A Ruxm are defined as the eigenvectors of the self-adjoint matrix AA', resp. A' A. corresponding which we always assume to be in non-increasing order. In matrix form, the SVD writes A = UEVİ where Diag((o,)))) (o,) while
singular values 0i 2 ... 2 nnmm
R V e IR. mxm are unitary in the sense U UT II and vtV = VVi = T. This implies that i == (u(i))(())) V(x,i) == (z(i) for all i [n]. so the i-th column of U does not exactly contain the entries of i-th singular vector. Given E mAAm), we write [A], U, V for the SVD truncated to rank and [A]ar A- [A], US, U,,
Norm of row vector If f E IR" is seen as column vector, we define the row vector f by f"(1 == (i) This allows to have (f.g),- = f'g. Conversely for a row vector p we define p¹ as a column vector by pi()) == p(i)/u(i). We then define (R) norms of row vectors by the fact that || = [l (w) where p is the Hölder conjugate of p. defined by 1 + = 1. In particular note that for indicator vectors,
1
[1llew = =Vll)))=(())) m(1),
(8)
Vu(1)
26

---

Matrix norms Given a matrix A é R= and p.g [[1, o0), we define the operator nomm
|Af
| (0) == sup
fcR
If
f+0
Since the eth (n) norm does not depend on measure, will write more simply e As for vectors, we may also write more simply |All when the underyling measures are clear. The ll-122,2 norm will also be called spectral norm. Our definition of row vector norms made to ensure the following property: if is row vector then we can also upper bound || |pl, ||ll... For later use, we also recall the standard fact that
| p.q = ||4 |1
which is a consequence of Hölder's inequality. In the sequel we will be specifically interested the following norms, that can be distinguished in two categories:
1. unitarily invariant norms, including the spectral, nuclear and Frobenius norm, which respectively the 10 ee, norms of singular values:
1/2
11
A || = |A|. = Σ Os: 1=1
IA -Ml=-t(6h (rn==((AAA)1
Σ
(10)
2. "entrywise" norms:
1/2
A( (4()
ol = max Σ (A(i,)),, (e[n] je[m
|| = max s9[n]
Σ
(11)
[j[[m]]
Unlike unitarily invariant norms, these depend on singular vectors: for the two-to-infinity can make the dependence explicit the left singular vectors: it is easily checked that
max Σ (z) |A
(12)
xc(n)
By duality 9 ||
- = max Ea1 (j)2. Note the inequalities
|1 11,,,
1/2 1:/12
(13)
for all ||||| (11112.2 11 p. ou as well the submultiplicative inequalities
|AB|, 2, $ |All d0 |
|AB|,, S | 00 2
Stochastic matrices and invariant measures We will often use an arbitrary measure, but in the context of finite Markov chains invariant measures are the most natural choices. On top of giving probabilistic meaning and making link with mixing as argued Section we will be moslty interested in invariant measures to obtain contraction properties. Given a stochastic matrix Pe Ruxm it is readily seen from 11] that [
1. On the other hand
00,00
EmEng ((i)P(i.)
P
|Pll1,1
]E(m)]
m(()
hence |pt|] 00. S if and only if uP S μ pointwise. If = m, this forces μ to be an invariant measure. The Riesz-Thorin interpolation theorem then implies that |P p. $ 1 for all p [1, oo In particular this implies that the spectral norm |P|l,,2 a (corresponding the all-one eigenvector and singular vector) and all singular values are bounded by 1.
A.2 Spectral recoverability: Proof of Lemma I
Proof of Lemmal 7 that
From 12 and the definition of the spectral irrecoverability we immediately
M [M],, Σ ofv((x)² < (+M)
ier-1
27

---

B Sample Complexity Lower bounds for
||
||2,00 Guarantees
In this appendix, we provide minimax lower bound the estimation error of (non-shifted) successor measures under a generative model, i.e., when observing independent transitions of the Markov chain. Definition 5. Let P subset of stochastic matrices of size x Given P PeP and vector Z e N with non-negative integer entries, consider family (e e ([n] x [m]]" obtained by sampling Z, transitions under P(i,-) for each E [n]] independently of all other transitions. We write Pp for the law of (Iz, Us T Given map f : P Rd norm |-| on R > 0 and e [0, an estimator M of S(P) is said to be (s, 6)PCC with for P and the norm ||||| if for all stochastic matrix P e P, Pp [ [(P) =.
The following proposition shows the sample complexity of estimating of the successor measure is essentially the same as that of estimating the transition matrix itself.
Proposition Lei PE Ruxn be a stochastic matrix and 7, e [0, 1). Suppose M is (e,
estimator of M = ( for the norm ll-loo,,o' Then P == } - --- is (4:/7,
estimator of P for the 1.11,0,00 norm.
Proof. Suppose | M
SE. First we show M almost satisfies the Bellman equation: using
00,00
that M P
M - (I+ (I+
= ||(TT -I( - -M) 00,00
11 ||M - M)
(1++7 |
22..
Then using yp= I --M
[n P) (((P-))]
1 - M >PI 00,00
I(T - ~PMM)
| 1 7PM
M
00.00
00,00
28 [ 11---1 1-
4s.
By the previous proposition, we are led to derive a lower bound on the sample complexity for estimating the transition matrix.
Theorem 5. For all integer n large enough, for all x E [1, there exists family P. of Markov chains on [n] which satisfies:
(i) every P e Pi is reversible with uniform invariant measure,
(ii) for all Pe Pus we have E(P) S K,
(ii) there exists universal constant C such that for all O, (Eus(n) Zo) -2 max(n, then there exists no PPAA estimator for Px and the I'll,,, norm.
In (68) Theorem 2), the authors consider the problem of estimating rank r transition matrix from a trajectory and prove minimax lower bound on the sample-complexity of order rn/s². Our lower bound attempts to mimick this result by replacing the rank with the spectral irrecoverability. but only proves lower bound of order max(n, x²)==² Our class of examples is based on block Markoy chains which allows to express the spectral irrecoverability as that of a smaller chain (Lemma 3 Intuitively, the sample-complexity > that of learning the smaller chain, while n is the complexity required to learn the partition into blocks. To get lower bound of order kng-2 we believe it is necessary to consider a soft partitioning of states, a.k.a state aggregation or mixed membership model as in (68). However we do not know how to extend the result of Lemma to that case.
28

---

B.1 Block Markov chains
Our class of examples consist of Block Markov chains similar those considered in (56).
Definition 6. Consider a Markov chain on [n]] with transition matrix P. It is a block Markov chain with blocks there exists a stochastic matrix Q on [k]] a partition of [n] into & subsets Vi,..., Vx and stochastic matrix p e RRxx such that
(14) where we write (x) for subset of the partition containing z. Furthermore we require that p(i,x) > 0 implies V,, which implies that (14) writes matricially as P Qp. We call Q the inter-block matrix and the emission matrix.
Vx, y [n]: p(z,y) - (()))
Lemma 2. Let P be a block Markov chain with inter-block matrix Q and emission matrix p. Then for all invariant measure y of Q, pp is invariant for P. Secondly, when these measures are taken as undertying the notions of adjoint, we have pp" II and
P P-p'Qp-
Proof. Suppose is invariant. Then we check that for all y e [m]]
Σ (p(x)
Σ
2c[n]
[[[k]_0e[m]
E (()p(=))(((:VV))))VV
is [A]]_q[[
Σ (()Q(((())))(((())
up)(y)
The second and last line have used that p(i,x) implies e V2. This is also crucial for the statement: computing the adjoint of p we have
p' (x, ())p(ii,)) l.v
up(x)
Thus pp' and p(x,y) Ei.je[k] Izev, ((. Qp(2, v) for all v.y [n].
Our interest for block Markov chains comes from the following.
Lemma 3. Under the assumptions made in the previous lemma, E(P) = E(Q). particular
E(P) S *min'
Proof. From the lemma, we can thus compute pt = =p'Q"ppp and
PP = ppt=p''m Q'QQ'p. p.
P'P=p'Q'Q2
In particular this shows that if Φ, resp. v is right, resp. left singular vector of Q associated with singular value then pi resp. s is right, resp. left singular vector of P associated with singular value a. Note also that P is a rank & matrix so non-zero singular values are obtained this way. Thus from Definition 3
max Σ C(P)
o (x:)) je[k] E1
max Σ (+1
1
B.2
Proof of Theorem
Our class of examples for the minimax lower bound are made of block Markov chain as described the previous section. We consider in fact two different classes: for the first one we fix block partition and the emission probabilities, and make vary the inter-block matrix, while for the second we fix the block partition and the inter-block matrix, and make vary the possible emission probabilities. We build these using similar process for the lower bound for reward-free ffre RL of (3I)
29

---

Lemma 4. Consider an integer n 2 0 and A, == {be (-1,0,11 E,d, = 0}. If n is sufficiently large there exists a subset Bn A, such that
(i) Bal 2 e
(ii) for all + B,, |b 11 m=1
Proof. If n. is odd, simply set the last entry of all b to (hence the n in (ii)). Therefore suppose now n is even and write n 2m. We construct the set at random. Let by e A,, such that bu(i) = 1 if i e [m] and (i) - i [m 1, 2m]. All the vectors of A,, can be obtained by permuting the entries of by. Consequently consider the set
B {S,bo, i [N]]
where ( are independent permutations chosen uniformly at random and (k, 11 (k) is the permutation matrix of o, By union bound and symmetry for all 2
PP [3b + b' B, ||b 11l1, 2 N(N - 1)P (1 bol 2
where S is the matrix of a uniform permutation. Observe
Sbb boll1 =2 L La(ismm +2
Σ Lo(i)sm i=m+1
i=1
= AL,(() = =2 i-1
where Ar,j = ligm.jom ism. Since this matrix has its entries in [0. 1J. we can apply Chatterjee's
concentration inequality for uniform permutations (10) Prop. 1.1) to X E Air(s) to obtain
-2
P P[ - 2m| 2 []] s 2exp
8m +
We deduce that with probability at least 1 2N 1)e-m// all pairs b V/ e B satisfy |b- 1/11 n/2. Thus by taking N en/44 this remains larger than 1 e 0(m) for large enough the set B satisfies the requirements with positive probability.
We construct and the partition [n] l 1)mm= im] U Vi. For the first class, let Q be any reversible Markov chain on [R]] with uniform invariant measure. Then given e (0, 1/3) and a family of
classes follows. Consider integers k
large enough, km
vectors (b:) } e Bk taken from the previously constructed set, define for [k), e [n]] the
emission probabilities:
(n (1 = + 3eb mod m)
(15)
Having e 1/3 and by 0,,,0,1)* 1** makes the entries of ps non-negative, and the fact that Σ, dx( 0 implies that Σg Pp (i, y) = 1, pg defines a stochastic matrix. Then let P3 be the block markov chain with block partition - V,, inter-block matrix Q and emission matrix pB- We construct the first class (( ::::=:(pp (Pn))BBs as the collection of such matrices for all emission probabilities.
For the second class, let be the uniform emission matrix, defined by Po(i.)) y) 1/mLgeV, We then want to use the B& to construct a family of inter-block matrices QB. however we require the chains to be reversible. A simple way to produce reversible is by considering a random walk on network: given a non-directed graph G on n vertices equipped with non-negne negaative weights (c(e)) on its edges, setting P(x,v) y) = c(x,g) Σ. c(x.z) defines a reversible Markov chain with invariant measure ((x)) Σy c(r,v) proportional the sum of weights. Thus we will use the set By to define weights.
Given a family of vectors (bx) B define
en(i,) 1 3sb,
(16)
Since e < 1/3, the weights are neg-negeeive and we can define stochastic matrix QB with transition probabilities proportional to the eg. It is automatically reversible, with invariant measure at i being
30

---

proportional to Eje[m] (s(i.)) = k, so the uniform measure is invariant. Let PB be the block markov chain with block partition U._ V,, inter-block matrix QB and emission matrix Pu- We construct the second class px()) 2) == (PB) BeBg as the collection of such matrices for all inter-block matrices. Finally let Pk p u pP()
Lemma 5, For some constant 0, k.m large enough we have
if (Ene[m] Zz) s C there exists no (c, 1/2)-PAC estimator for the class P! and the 1o norm.
if (Enq(u)) 2x) $ kk there exists no (e, (/2)/PAP estimator for the class p(.) and the ||1low, norm.
&
Proof of Theorem Given 2 1, let k: [K] and define the family Pk as described above. Every chain of P E P is a block Markov chain with inter-block matrix Q which is reversible with uniform invariant measure, hence Lemma 2 shows that P P is also reversible with uniform invariant measure. Then Lemma 3 shows E(P) {(Q) & & K. This proves the class P satisfies the requirements (i) and (ii). Finally Lemma shows (iii).
The proof of Lemma is based on Fano's incquality, as stated in (3] Lemma D.10). Proposition 4 (Fano's s inequality). Ler Pı..... Par be M probability measures space Q. For any estimator on Ω
inf 1. ΣM KT,(P,, Po) log
1 11 M M
log M
where the infimum is on all probability measures on
Proof of Lemma 5 We start with ((1). Consider PB, PBr E (()). If PB + Par there exists æ [n] such that Pn(x,)) Pn (I, Then by construction
&
|PB PB lo 2
Σ
PB(2,.) PB. (x,
y=[n]
3z
Σ
(v) - (V
n ycfm]
3z
35 (1 1/n)
- -b(())-brro))
n
by the second condition of Lemma For n large enough this is strictly larger than e. Thus an 5)-AC estimator of Ps for the ||+ norm yields an (c, 8)PCC estimator of B. Given stochastic matrix P on [n]. let us write IP for the law the process generated when sampling independent Z; transitions at every state i. Thus by Fano's inequality (Proposition 4
EBas. KL(P Pg KL(PPg. Pr.) log
Ppe
B [ B3
P.P
BK m
log
[3
BeBk
for any stochastic matrix Pg. The process generated by P a product of independent multinomial Multinom P(i..))) thus we can compute
P(x, v)
KL(P
Σ Z, Z.P v) log
Q(x,
[.
31

---

We take for Po the block Markov chain with partition (V)). inter-block matrix Q and uniform emission probability po(i.y) 1/mmlyv; Then exploiting the block structure we have
Ps(2,8) Pr(
PP))).PP))
Σ ZeP ZgPB(I,8) log
z.ye[n]
(V(V())) Po(V(y),
Σ 7 VLQ log
z.ye[n]
Σ Σ Z=Qo(((s),))))((tu))) log
Po(i,
zc[n]
Now for every ie [k], by 15
pb(i,8)
1+3eb,(i)
Σ pb(i,) log
Σ
log (1 3Eb,)
veV,
Po
je[m]
m
be)
$ Σ
3ebx(j)+
]e[m]
m
s 9
The second line uses the inequality log(1 u) s u, the last line is the consequence of having Σ, b+(()) 0 and b,())² 1). Summing over i get
KL(PPn,,PM PP) s 9
Σ Z
[[n]
so all in all we deduce
9ea 9c²(En EEee(n mm] 7x2) log
Σ
Ppo
B B
1/2
B
log B
BeBk
(Eze(n) Zx)
S
log((B,))-22og) 18c"
By Lemma log B 2 km/40 40 n/40 therefore if (Ene[n) Zx)
x/40-2 2og2 there exists no (s, P/CC estimator of (())) This proves the first statement. 18g2
The second statement is proved similarly: above (s, PPAC estimator of p( necessarily yields an (c, PAC estimator of E B. Applying Fano's inequality with Po the matrix with all entries equal to 1/n, we are now led to compute
Σ Z. (vQ)(V())) 1
log (QB(((E).V(I)) m
KL Pa Pp:
2.y[[n]
m
Σ
Σ
2 Z.Qu(1,)) log (i.)))
[ DeV.
1 3ib
Σ
Σ
log (1 + 3rb,
[
VeV.
after which the proof follows the same arguments.
32

---

C Discussion and proof of Theorem |
In this appendix discuss limitations and possible extensions of main result, Theorem | state few key intermediate results used in the proof, and proceed to the proof.
C.1 Discussion
Control of the singular gap We suggested that Theorem I requires in practice a large gap A, := o, 0r+l- From the obvious upper bound A, S oy. the best can hope for is having A, 2 co, with a constant e < 1. The following lemma shows that with bounded spectral irrecoverability we can always achieve A, c up to small look-ahead in the singular values.
Lemma 6. Let A E Ruxm. Then for all there exists r' r such that
(1-1/e)o, 3E(A)
0p+1 11-
Or- and or 2
Proof. First we bound Σi= S <E(A). Consider now r E [n]] and an arbitrary integer / 2 1. If Ortit1 (1 1/1) for all i [0,1 -1] then
Σ o (r 1), or Σ (1-1/11) 1/1)² 2 or 1-1
-1-1/(111//)" IJ
1=0
2 2 - 1+ 1 (1-
where we used the bound - 1/1) se 111f/ S se_1. We thus get contradiction if the right hand side is larger than E(A), which occurs if 2 1-1/c
1 ((A) - r Thus by taking 1= 1-1/e ((A)
there must exist s (- 1 such that or+i+1 (1 1/1)a,-i. From its expression we can bound 3E(A) while by taking the smallest possible we also have 1 s (1-1/e)o.'
r++ (1 - 1/1) 0, 6 2 noting that 2 and using the incquality log [ --) u) 2 -u/2 for S 1/2.
Extension to non-recurrent Markoy chains Our result requires v to have full support and to have its density w.r.t. invariant measure inv bounded from above and below. This apparently rules out absorbing chains, and more generally chains with transient states where invariant measures do not have full support. We argue however that our result could also be applied in that case by decomposing the chain adequately. We can decompose the state space X' = U R2 U Uا Tj into irreducible recurrent classes R, and irreducible transient elasses T, (for all x, y E Ty there exists a path of positive probability entirely contained in T,. but the chain eventually leaves T₃) (see (7). Our result could then be applied immediately on each R, by taking the corresponding invariant measure, but could also be applied to Tū as well. Indeed, an inspection of the proof reveals the only reason we require the invariant measure is to have contraction properties for Pn, in e (N/,,in),, which holds if P is substochastic and v is excessive. in the sense vP, 2 pointwise. On a recurrent class an excessive measure coincides with an invariant measure but on a transient class Tj an excessive measure is quasi-stationary measure (4), which describes the asymptotic behaviour of the chain conditioned to never leave Tj. It can be obtained concretely as follows: restricting Pz to transient class T; gives substochastic matrix with non-negative entries, so we can still apply the Frroon-Foobenus theorem. The first left eigenvector is the quasi-stationary measure we are looking for.
Dependence in and Va.ine We have already explained after Theorem I why consider two measures: y is known by the practicioner and used to compute the SVD, while the invariant measure Uxyiny is more adapted to the analysis. Our proof makes use of very rough comparison of the norms to relate the two and there is potentially room for improvement.
Dependence in the policy π The very core of our proof relies on concentration inequality for P E R** (Theorem 8), which is independent of a policy. This is the key argument to obtain an off-policy result, which could also be used to make the result of Theorem [ hold simultaneously over set of policies (assuming for instance bounded density w.r.t. reference policy). We are limited however by the invariance properties required for the measures, so we have preferred to state the result for fixed policy only.
33

---

Dependence in (1-7)-1 Supposing that k s (1 (1-2))1 our estimation error (2) has a dependence in (1-7) which means that the sample complexity of our algorithm for estimating the (shifted)
successor measure with e-accuracy scales (1 70- This is probably sub-optimal, as learning an 6-optimal policies (in reward-specific RI.) should have a sample complexity in (1-7) -3 (4)
Further note that if one attempted to apply our result for the family of policies considered in policy improvement scheme, we would typically require an additional factor (1 (1-7)-1 the sample complexity. From these observations, we conjecture that the sample complexity of estimating the (shifted) successor measure should scale as (1-7)-2.
Dependence on the uniformity of the measure Our result also features a ratio v(s,a)
max(s,)) ('')))) (z.a"(" over all pairs (s, (s', This forbids highly heterogeneous measure but we believe this could be an artifact of the proof. For the most part of our argument, in particular for the concentration in spectral norm (Theorem 7. we are led to consider ratio only over neighbouring pairs, i.. such that P(s, a, s's)
s')> > O, which can be much smaller. The consideration of ratio over all pairs come from rough comparison between the 2 co and spectral norms in the leave-one-out analysis.
Bound for the non-shifted successor measure Finally we note that Theorem D can be used to derive a bound on the estimation error of M, in ||- norm:
[Max)]] -Mall S CErstim + Eapppoxx 2k-y.
(17)
This based on (40) Lemma 24.6). Let X denote the chain with transition matrix Pz and let T ~ G(1 7) be geometrie variable independent of X taking values in {0, 1,...). Note that M, = (1 - B [T] and Mn, (1- [ [PT**
Then writing 1 -llyvyy for the total variation distance between two measures J4, U, it is simple to notice that
1(1-7) (1 MM
2 max |P& [Xr = .] - Ix = -llv zeX
$ 2 [T [T T + k= -
(1
by 44 Lemma 24.6).
C.2
Main steps of the proof Theorem
The strategy to prove Theorem 1 consists in the following steps: we first prove concentration bounds for the simple estimator Mr in spectral norm and strengthen them to 2 oo norm. We have summed up the main steps in the diagram of Figure 5
Thm.8, App.E E
App. F.1
Thm.7, App. F.2
Thm.6, 6, App. D
Concentration inequality
Control of P
Deterministic
Control of P
Deterninitic
Control of M Ma
Control of
Stein's
contraction properties
"mean-value' inequality
Leave- one-out analysis
M n2
Seectal norm
|| (1e (lyran))
Entrywise norm || Ilee e
Technical concentration
inequalities, App. F3
Figure 5: Main steps the proof of Theorem
We focus on the latter part of the proof first, i.e., obtaining bounds in entrywise norms from bounds in spectral norms. We state a general result for the estimation of a matrix, based on the so-called leave-one-out analyis (I). The proof is given in Appendix D
Theorem 6 (Leave-one-out analysis). Let probability measure on [m] with full support, M, M e gaxx be positive semi-definite self-adjoint matrices w.r.. and E == M - M. Write M U
34

---

M = UAV for the eigendeccompositons of M and M respectively. Let r E [n], H, = U, and A, == X,(M) 1 (M), with the convention that Xa=1 (M) :=0. 0. Suppose there exist A, E 0 such that (Urle(()) & Ae, EM e(v), S & (0)) and
As 1&1u, 1eluleecw))
U.CC.H,-U:lleooa U,)le Se (12,lH,- Ur Urlle -UT,H,--Ulllees,eeee
A,
Then there exists universal constant C > such that if D./4A
CAI (e())000
|00 H, Urllea 5
(18)
and
CAlAl | [AI Me
|| [[M]+]]]]] ((U),
(19)
Drla,
The previous result requires several controls the error matrix E in spectral norm. The bound required on Ellee))))) will be the consequence the following, which is an analogue of Theorem for spectral norm. Note that the underlying measure is here required to be invariant (we explain how go back to arbitrary measure in the proof of Theorem 1.
Theorem 7 (Concentration in spectral norm). Let P TR-x'S be the transition matrix of a finite MDP. Let μs be a probability measure on S. policy and v(s, (s,a)) = (()) a), which defines probability measure on the set of state-action pairs. Let 1e 2 0, E (0, 1) and write
$max(k,(11 (1-7)-1)
Cke
1-7
For all policy n, for all 2 if is invariant for Pa then
-12 min(sa)-)(
Zeau(e',a') ((s,0)+0((55e)) 8Ck, + (t+22k.)))
P [[ Manlless) 2 4n exp
Recall that n denotes the cardinality of X. The minimum here over pairs (s, (,,a),(5 (s',a')) X such that P(s.0. a, a') 0.
The proof of Theorem 7 can be split in three main steps: we will first prove concentration inequality for P using Stein's 's method of exchangeable pairs (see Theorem & in Appendix E We will then extend this concentration result to P,, and Mr,A k using deterministic arguments in Appendix F where we will also establish set of technical concentration incqualities, gathered in the following lemma. Given l [n]. let
P() = P+ -,,
(20)
where 1, denotes the column vector with coordinates all equal to 0 except for the 1-th, equal to 1, and P(I,-) is the 1-th row of P. P()) is the matrix obtained by replacing the estimation of the We also write
1-th row by the true value of the matrix P, so that P()) = E [
M79 T.K
(()) (I (()--
Lemma 7 (Leave-one-out concentration). Let P X be the transition matrix of finite MDP, e R Sxp π be a policy and v, be probability measures on [.[p) respectively. Suppose v is invariant for P For some universal constants Ci, C2 the following holds. Let k 7 E [0, 1) and
Ck,y == C1 max k: (1-
1-7
35

---

For all LE [n]] and t 2 0 we have
P ||| (1,))))) NO (1, ) ((
2t (Yaas)
-12
(k++)) exp
exp
(21)
C2 |Al (0),
P
I Mr 100, 2t]
-t2
5n(k+ (p exp
(22)
C2 |A
P
Mn Mr AA- Ma A 2t
-mini- 2.v(1)
-12
((8))
$ (k+ + 2) + exp
+ C2kpmexp
(23)
(()) (l)]|A|pu |A
Zar(i) -f2 minin
P M Ma Maslleecs 2 4nexp
x(1)+t()
(24)
8Ck, (t 20k,
|
00,000
C.3 Proof of Theorem
We now apply the results of the previous subsection to the estimator of the shifted successor measure. Fix policy y (0, 1), & 2 O and Mr.* P - P Recall the estimator Mr := Ph - Px) Since the arguments require self-adjoint matrices let
Mr.
Mr, Mr
M := M
M
(25)
and write == M M. Let (o (. (o,) be the singular values of MR,K and M arranged in non- increasing order, and M = UEU", M UUS be the cigendecompositions of M, corresponding to eigenvalues (A (T)) arranged in non-increasing order of absolute values. These are related as λ25-1 ss A2r - for all i [n]. We need thus truncate the eigendecomposition of M and M to rank 2r, however for notational simplicity, we write r in subscripts instead of 2r except for Daar but this is o, by what precedes.
Proof of Theorem In this proof we write $ if there exists a universal constant C' 0 such that as Cb. Set
max(k;(1-))) (1-7)-1)
V Vn.inn (s,a)
log(krn/8)
(26)
1 1-7
(s,a)
Zo Ur inv in (8', aa)
(o
Our goal is to apply Theorem 6 with M. We thus need to control E ((())
|EMlle and
L,, (UUU,HH-UU>lllroa.... U,>lll which we will bound using Theorem and Lemma 7 Note however these
only provide bounds in spectral norm with respect to inv. while we need control with respect
v. We address this issue with rough comparison of norms: for all f IR", we have
du
dd/ du
If l
If
(
dum,iny
which in turn implies the comparisons of matrix norms
dv du inv
dv dvn.inv
| (Blew)))
B (ooc) ) (V
(27)
1oo
dv
36

---

and
duv dv
| [Blle
| (os d.m
(28)
dv
B ( dVT inn
|Blle
(29)
for all matrix B. Write A
dv
du dv
Thus up to factor A, use the
di
concentration incqualities in spectral norms with respect to ,aii Note the maximum over all pairs (s,a) in the definition of (26) upper bounds the maximum over neighouring pairs in Theorem 7 Thus if the values a suffciently large to make $ the theorem and (27) show that
E (llee $
[Elle & As
(30)
with probability at least 1- 6.
Similarly Equation 22 of Lemma shows that with probability at least we have
ee || MMaas,,
Finally we claim that with probability at least 8 8
H,, -U. se (1, Ur lelss
Ae UU [Uelle(),
(31)
A,
From Theorem and union bound this will sufficient to get that
Ao1 || MM
M -Ma & or Tr+1)
with probability 1 - 5. Theorem follows from observing that MMla
1| (es.ellec (u)) that Mx,inv in the definition of (26) can be replaced by at the cost of an additional factor A, and using Lemma 1 for the approximation error.
max
Proof of the claim 31 We now prove the claim. Given I 2 1, recall the definition of P(1) in 20 and
let M() ( etc. be the matrices obtained their general counterparts M, Dr. etc. but using p()) triangle inequality to bound
instead of P. First
E,,,H, U.) U.)le
max (U, e()) ((L,)) H.O U.) (9()))
[4[n]
[[,,,, -((() (..HH(10) e
< max lé(m]
max lc[n]
The first term is bounded as
EE(,)) -0,0 H Mees
s 11 Ele (3( U,H,, -(.) H!")) ((()))
Vx juv (1)-1/2 (l (,
10,H1 - (((1) _1(1)
(
S Uz, inv 1/2 1 0.01) H((1) (e (32)
with probability at least where in the second inequality used
On the other hand since (0, HiO) U,) is independent of Yú, Equation 21 of Lemma 7 proves that conditional on (Ys,,, (s,0)tt, with probability at least 1 1
(T() H.O U,)le s 1 H - U, e(v),
(33)
37

---

The latter norm is bounded as
|000 H
Urlle Urlee $ $10,00 -U,H- + 10, - -Urlees
s min 10,-0110-- U, U, -, -U
11/2
(34)
We are thus left with bounding
1 H H, (
U,Ü,U -.
10:00:00 (0000000-,00:1.... -,,0, (( (Ullees
10:00,00- - -0,0%
|
-,0;
$
du
From the Davis-Kahan inequality (Prop.
7
(M M )7.00 (()))()))))
o.6 -
1/2
2
(M MO)
Jine
((v), (v
0(1) -((1)
-r++1
By Weyl's inequality (38) for all [n]] we have (((0 oi S M M (w) which is
below As up constant factor with probability at least 1 - 8 by 24 of Lemma 7 Hence (a()) -2 ) 22 if Ae /,, and we can bound
A (M M
1 HHOHHH) H ((x,,))))
((V))
A, Now comes the point where we use that the maximum in the definition of involves all pairs x, x' e X:: has the consequence that
Un,inn (1) Vnr,inv (1')
Ze inv. 1. Vs inv (1)
max x.2'EX'
ZzUxziov
Therefore these term compensate each other when taking t EV EV2/2 1/2 which thus implies
min, in Equation (3) of Lemma
(M M() )( (v( ind) $ eu 1/2 i min
(7(0)
min
(((),
with probability at least 1 5. Then using Lemma we bound
1 lew s2 $2 (1 Maw
11 s ( H. Ur U.lles() +2|Urle
Combining the previous these inequalities get
Aa M- min 10,0HH0 (0 -HHHHlll,)Hl $ A,
11/2
+ (10,00 H -
(35)
and plugging this in 34 yields
( H - Ur -Ulle $ As
A. (10.0) H(!) - -Ur -Urle()) || |Urlle())))) +108, 11, -U, ((())
(36)
38

---

so if As/A, is sufficently small regrouping the two identical terms yields
1 H U, (()), & |U, - -Urlee + Ae
(37)
D.
Plugging this back in
35 get that
AE |U,H, Unllew A,
Ae A??e2
1/2 x,lav min
AE 10 ( U, ((v),
-U,
(()), (Veriuv)
A
A?
A,
All all combining
32 and
33
EU - U,) U,) (l is upper bounded by times the latter
equation
37
we obtain
A=² 4, (IU,H, Ur Ue(e (Urlle(w)
E(U,H, - U.) e0
(I, - Uillew)) Ae [1rlews
A.
se (10,HH, U. (e()) A.
AE (U
using that As S A,/2, which proves the claim.
39

---

D Entry-wise guarantees: leave-one-out analysis
In this appendix we prove Theorem 6 The argument is based on the leave-one-out analysis introduced by Abbe & al (I) but our proofs are more aligned with the monograph (I3). Overall, Theorem 6 is obtained after few modifications in the proof of [33 Theorem 4.4). In all this section, we consider to be probability measure on [n]] which for simplicity will be omitted from notation. The norms ||-1 with no subscript at all refer to the spectral norm |-12,,2
D.I Entry-wise guarantees for SVD estimation: proof of Theorem 6
The theorem will be the consequence of the two following propositions. We use the same setup and notations for Theorem 6 We recall that H, U.U.-
Proposition 5. Provided |U $ 2, we have
|EM 2,00
1+ 4 4|EU|1 4 M|| 2,00
|EU,|
|U Url12,00
|Ar|
Arl
|rl
A,
2 E(U,H, H, U2))11,000
Arr
The following proposition shows how the control of the eigenspace via U,H, - U, implies a control on the matrix [M], itself for the two-to-infinity norm. Proposition Provided EU, A
[M - [M] 2,00 Mal U.H, Ur| + +4 ||EU,| (20,² 12,1-t)
Proof of Theorem
0
Use Proposition
5
and the assumptions to bound |BU,||
||
S Ae and
Ü, H, 12112,00
M 2,00
4As)
4A |
12,00
2,00
&
1 1
1
A
Prl
|xp1
Ar
2s [
| - U,
Ae UUTrl200
2,00
D
If E $ A,/4 then 25 s 1Apl /2 so we can rearrange terms to obtain
10,H, - Urll 2e |
4Ace
8AIM
12, E
1
1
1
[xr
4 |U,
|U,12,00
Ay |xr
Then use the crude bound |U+ 2.00 S
||U,Ar11,, |--I-' |M Keeping only the dominant
term in the right-hand side and plugging this bound in Proposition yields the results. D
D.2 Technical lemmas
We now prove Propositions 5 and 6 We start by gathering three basic results that will be used in the proofs. The first one Weyl's inequality, which states that for all matrices M M ppn for all i [n].
(MM A < M-M]
(38)
Then we recall the classical Davis-Kahan inequalities. We refer to Corollary 2.8 of (13) for a proof. Proposition 7 DDavis-Kahan inequality). For all r [n]] if M - M| s A,/2 then
(M M)U,l
-,,
A.
40

---

Finally we will need one more lemma. Given matrix A with singular value decomposition A UEV", define sgn(A) = UV!
Lemma 13
Lemma 4. 4.) For all r 1,
|1, |gn 2 E
(39)
A
Furthermore if || A,/2, then
|,, 2.
(40)
We can now move to the proof of Propositions and 6 The following lemma is taken from Lemma 4.16 of (13) and is an intermediate step towards Proposition 5 The only difference is that we do not assume to be rank r, but this has no consequence on the proof.
Lemma 9, [Lemma 4.16] Provided | S 4
2 M(U,, U-)
4 M
2,00
FUU
10,H, MU,A," 2,00
S
|Ar1
and
H,,
4 M| 2,00
|EU,
|EU 2,00
JU,HH -U
+
(41)
|A,1
D.3 Proof of Propositions
5 and 6
Proof of Proposition 5 The proposition is simple continuation of Lemma 9 The first term of 41 bounded using triangle inequality
MMC,H, - 1, ||M, (|,,,,,, -,)
s || 00 |1, |
E(U,H, U.)
Since U,U,- I, one can notice that
||, H,, - U,| 10,00,,,UU
-,,0,-
Using the Davis-Kahan inequality (Prop.
can thus bound
2 12 1EU
MMC,H, -UH,-UU,) U,,
|E())
(42)
A.
Similarly the second term of (41 is bounded
MU, 2.00
$ <|MMUrl22.0 + EU, 22.00
$ + +|EUrlla,
(43)
Finally we bound |EUr,l,, < | s s/A and 43 yields the result.
|EM1 so combining
41 with
42
Proof of Proposition 6 Using the SVD decompositions of M and M,
M - [M], C, - U
= ÜÜ, (A, -H,AHH,, U +UHHA,HHH -U,AUU"
(44)
41

---

Bounding U, (A, H,A, H Using MU, U,A, and U,M = A,U!
H, H = - - UM E)U,
=,,
and thus 8, H, -UA
HÜ Then note
|U.A,122-- = ||M 112,000
$ $I[M) - [[M) + 1M
and in particular
| U, 2,00 $ x
- (I[M)--[M-ll.... 12
Thus we can bound
[0, (A, - H,A, U/ < <|0,Ar
2,00 - 1 |T, |U, HU,
(I[M)) [ [M]r
+ -1 (1) H, H X, (E,I))
By the Kahis-Kahanaaa inequality (Prop.
4 ||
I --H,H:1|-1000 U 1| $ A
Then if |E| s A./2, Weyl's inequality implies X, A, - || 2 X,/2 and we can bound
10, (A, H.) ( 02 2 (I[ [Mrrl
| ||U, (A,, + x,²)
|
If furthermore |EU, 4,/8
make the factor in front of ( 2,00
smaller than
1/2 so by rearranging terms from (44) we get
[ - [M]rl1,, s M| 2, EUU -|
(45)
Bounding O,H,A,H,U U,A, One checks easily that
U,H,A, H, (U, C. The first these terms can be bounded as
[[C,H, -ALH,-U,))A U,)A,,,,,,, $ s1U,H, - U. Ur|1,,00 |A,|| 0, s |All H, - Ur U2112.00
the second as
(U,,, S $11U,A,,12,0 10,11,
Url
2 M |M EUr
A,
using the same bound as for (42) Finally the third term combines the two bounds:
100,1, (.-HH-U,)A,, (,, U,)' 2,00
10, - Ur|l2,00 ||rl U,HHH Up
2|A11 |EU, |[, 1r112,00
A,
|iil || [,
H, - U, Ur|12 2,00
4
if || |U, s A,/8. All in all, this gives
5 |
2 M| 11, || |EU,||
10,
S 4
- 2,00
(46)
2,00
A,
Combining the two bounds (45 and (46) together yields the result.
42

---

E
Concentration in spectral norm for stochastic matrices
The goal of this appendix and the next is to prove Theorem and Lemma 7 Instead of using off-the-shelf inequalities like Bernstein's 's inequality, we establish the concentration inequalities that we need using Stein's 's method of exchangeable pairs and more precisely the arguments of Chatterjee (TO). We thus establish general concentration inequality for the empirical estimator of stochastic matrix in Theorem 8 which to the best of our knowledge new. This appendix also gives a brief account of the method of exchangeable pairs for concentration and its extension to matrix inequalities developed (52 44)).
E.1 Main concentration inequality
Theorem 8. Let IR be stochastic matrix and p.v two probability measures on [m]] [n] respectively. Suppose that for each i E [m] we have drawn Ze independent samples from P(i,))
and for all j e [m]] let Yi count the number of samples with value j. Let P(i.j) = Yiş/ Zi be the empirical estimator of For all
-12 ming-j Ziu(i)
P [[
Pl Ple 2 s (n 3m) exp
+())+
8(t + 2 pr
20,00
where the minimum is over all pairs (i,5) E [n] [m]] such that P(i.j) > 0, and the adjoint P is w.r.t and v.
E,2
The method of exchangeable pairs
The method of exchangeable pairs consists eventually in establishing differential inequality on the moment generating function (m.g.f.) that can be integrated be combined with Chernoff's bound. In the matrix case, the argument can be extended to Hermitian matrices (and to more general matrices thanks to classical dilation trick) using the matrix m.g.f.: letting (r:= n=' Lr denote the normalized trace, the matrix m.g.f. of a Hermitian random matrix Z Cnnn is
Mx := Er e eER.
(47)
We use a lower-case denote the log of the m.g.f.:
mz (0) log (0).
We have the following m.g.f. bounds:
Proposition 8. (52)/rro.. B.2] Let Z C be Hermitian random matrix. Let Amax (2), Amin A denote repectively the maximal and minimal eigenvalue of Z. For all t e IR,
IP [mmax (Z) 2 t] n inf exp (- ft + mz (0))
(48)
050
P [Pmin (2) ) (] s inf exp (-01 m2
(49)
6c0
Suppose now = ((X) where X is random variable taking values in a Banach space and is map with Hermitian matrix values. We may write simply E [Ø]] for E [Ø(X]] An exchangeable
pair is simply pair of random variables (X such that (X,X) (d) (X,X) in distribution. The technique requires next find map K K(X,XXXXX X) such that
K(X,XX x) = X),, 2. E [K(X x] - [[]).
where write [[0] [xx) to simplify notation. Combining the two properties obtain that for any function h with matrix values
((((X)(((X) -[)((((X)BB(]]]]]] 1 (
43

---

= - this implies that Applied to =
Etr ( (6(X) - Etr ((( -(CC)))))))))))) X(X,))))))
One can then notice that E 6 (X) [+ My xx) (f). On the other hand, the right hand side can be further bounded using mean value inequality, which is straightforward in the scalar case while in the matrix case one arrives at the following.
o(
Lemma 10. [Lemaa B.4] For all 9 IR we have
| 1 | (xVo(()) VVVVV()))+VVVV())))+)))) (X))
(50)
520
where
Vx(X) (6(X) o { x]. Vx(X)= R K x1) x].
The goal is then obtain positive semi-definite (p.s.d) inequalities Va. typically of the form Vx(X) z >I + (.) Here we write = A is p.s.d.. This would result a differential inequality Mo(x)-E(o] (0) that can be integrated to obtain bound the log m.g.f.
702
(f) s 2(1 330)
which in turn translates to a Bernstein-like inequality for of by taking 0 == t/(++ in Proposition
g
Theorem A.
(52) 3.1] Suppose there exist constants 7. 0, 8> 0 such that
Vo(X) s 5
T+ Bx())), Vx(X) s s(> + (6())) a.s.
Then for all t 2
22
[[ (x(X)) 2| S exp
2( + 3t)
-t2
PP [ (x(X)) 2 (] exp
27
The previous arguments require the random matrix di X) to be Hermitian. The more general case can easily be dealt with thanks to a Hermitian dilation trick, namely by considering the random matrix (o(x)) )(x)).
0
E.3
Exchangeable pairs for independent multinomial variables
We now show how the method of exchangeable pairs can be applied to prove concentration for functionals of multinomial variables, which is the setting that appears in the case of transitions observed independently. Let P. gaxm be stochastic matrix, Z (Zi) deterministic sequence of integers, N := Σm= Z; and Y (Yi)sej=) a random matrix of independent multinomial variables with Y, ~ Multinom( Zi, P(i..) for each i. We write P(i,j) = Yi,/ Z; for the empirical estimator of the matrix P. All norms ||-|| considered in this section spectral norms with respect underlying probability measures μ1, V on [m], [n...
The first step is to devise nice exchangeable pair. A very natural one is follows: let I [n], J, K [m] be three random indices such that J, K are independent conditional on and with law given by
P Y Zi
(51)
Yo
P[J= = T=
P(ij), P[K k T T T P(i,A). Zi
Then let y == Y 1 To see why (Y, Y) forms an exchangeable pair, interpret V., as follows: consider N balls of different colors are distributed in ums independently, such that for each i,
44

---

there are Z balls of color i, which fall in um with probability P.y. Then the number of balls of color in urn has the law of Yu,, and Yıj is realized by choosing one ball uniformly at random and putting it in a new ur. It is thus immediate that (Y,Y) forms an exchangeable pair.
Given function di RRx Rn'xm', let AY)ō(Y) == @(Y 11ş)) +(Y). Note that if Φ is an afline function, A (Y) does not in fact depend in Y, so we may write only A,ÿ
Proposition Let Φb IRuxm R xm' be an affine function with matrix values.
(i) For all 0,
-t2 2N (Er, |Ar Er, |
- ( s] (n' + m') exp
the expectations Br,j,Ey, being with respect to I, K as defined in (51)
(i) Furthermore, almost surely o(Y) is self-adjoint and (Y) z for all i, then for all
0
-12
P -E[())]]( 2 n' exp 2maxx. A Gg e0
(t E [((())]
Proof. In order to apply Theorem A suppose first & to have self-adjoint values and will extend the first inequality to more general functions by a dilation trick. Note furthermore that we can suppose without loss of generality that the constant term of the function iz zero. Combined with the affine assumption, this implies that ø is linear and can be expressed as
<(Y) Σ (i.
with -, (Y) being independent of Y. Averaging over Y shows
E [[ 2(..)))
Then from the distributions of I,J,K [T1 we deduce
E[Ar | Y] N
oYY).
E[AıKø] Y1= N [[(()),
(52)
From these, we claim that K(Y,Ý) = N(O(Y) o()) satisfies B[K(Y, x] x(Y) (Y)-
E [[o(Y)] Indeed the definition of Y implies
s(Y) (V) AIJØ(Y - 1 Arx
(53)
so averaging over I,J, K and using (2) yields the claim.
In view of applying Theorem A
only left with upper bounding with Va(Y)
[ (0))(((())))))))))))) Y] and (Y) {E[K(Y, Y>² y]. but by what precedes VY(
NY)) Using (53) and the p.s.d-conexxity of the matrix square (ie.. ((1+t)4 tB)²
(1 - A)- + IB² for self-adjoint matrices A, B and l [0, 1))
Vo(Y)
[ A 2 y]
E | 2 + | 2 y)
E, | 1 E, ال
Applying Theorem with y N (Er,J A 1 2 E,, ا B and == N gives thus the first inequality.
45

---

If we assume furthermore all the A. are psd, the positivity implies we can bound
(قمr)) |ام A.j
max
Auoll Aij
k.l
for all i.j. Consequently,
Ve VV x max k,l
A
B Ar A Y]
N
max k,
A R (o I [+])
N max k,
A o (o E [Ø] (
by [5). Thus applying Theorem A again with N but this time 7 maxx. | [[]]] and
maxx, Aurl yields the second inequality.
Finally the first inequality extends to the non self-adjoint case by considering the self-adjoint o
dilation (Y) (00) 0 $00), ). simply noticing that [| E[v(Y)] |lx(() -
and | 0 (Y) =A)))
E,4 Concentration of the empirical estimator
We now apply the previous results in order to prove Theorem 8 Note that as function of Y,
A,j P Z. 1,13
(54)
P(i,)) > and otherwise.
The proof will require controlling the adjoint Pr, which leads first prove concentration of the functional v PPG) vP()), for each [n].
Lemma 11. For all j e [m]] 0.
Zx -t2 minnnss
P (omP(i))u((P) 2 2exp
v(1)
(55)
2(t+ 2v)(j))
where i denotes the fact that P(i,j)>0 O.
As a consequence
- min Zia(s) v())
PM
-||
(1p"l 2 emp
(56)
00,00
2(1+ P? 1oo,00)
Proof. Fix j e [m] and let <(Y)= uP((). This is scalar function, linear with respect to Y, with
v(1)
v(1)
0 A
Z: カ= S max ld-- Z₁
Thus can apply the second inequality of Proposition tto obtain the first inequality.
xP(1)
The second inequality is a consequence of the first: note that by and by union bound
00,000 = maxje(ml
P()
|
max pP(j) - -DP())P()))))))) 2 tp(ii) m=[
00,00
-iinn v(1)
Z,n(i)²
S 2m max exp je[m]
2(11(() + 22
-1.2 -12 mimin
Ziu(i)
m(3)
22
2(t+2115 100
46

---

Moving to the concentration of P. the inequality of Point optimal result due the additional factor N. To resort to the second inequality, we need consider p.s.dd. matrix. The idea is that for any square self-adjoint stochastic matrix Q. 7- Q is p.s.d.. Thus Q= - ( can always be expressed as a difference of two p.s.d matrices, which motivates us to also express our self-adjoint random matrix the difference of two psd matrices.
ii in Proposition does not yield an
Lemma 12. Let be a measure on [n]. Q IR"*" such that Q* Q with respect to ps and f IR".
= = and jii,)) s 0 for all # j. then
(Qf: (0-0)=-2 Σ (00
i.je[m]
In particular Q O.
Proof. Let f IR". Then
(Qf.f), =((()Q()))00
= -
= 2 Σ (()((())) -())) 20.
The second equality uses Q1 = 0. the third uses Q" Q and the inequality arises from the hypothesis that (i.,j) & 0 whenever i #
We use the standard dilation trick to reduce to the self-adjoint case, i.c. prove concentration of the (n + m) x (n m) matrix 0 5 with respect to the probability measure (M[[x] + M[m]). which gives the same adjoint operators.
Proof of Theorem 8
pr 0 ). The concentration is in spectral norm
Let D1, D2 be the two random diagonal matrices defined by (i = Eje(m] P(i,)) and D2())= = Eienn) /(i.j)/(() = Eie(n] ().) Note that Dj evaluates to the identity matrix, however not equal to the identity as a formal function of the random variable Y. One can then express
(
0
P
D
-
0
D
-P
pt
0
0
D2
-pt
D2
and thus
p PP P|| Amax (00) 0,)
))
Amin ((B) -p)) -
(....) B[D2)
p(ba))
(57)
Notice that the norm of the diagonal matrix D2 is D21 = maxje[m] from Lemma 11 we have
vP(j)/m(i) Pt
SO
0o, oo
- mmin
Zen(i)
P Xmax
(0o D.))))) -
B[D.] 0 m(ra
2t < 2m exp
v(1)
2(1+ 2 pt 1o0.00)
-12
s 2m exp
(58)
2x(1 + Pt (00,00)
where we write ::= maxi-j +()+t(() 2,r() Thus it remains to establish the concentration of the matrix
== (_))) -.). for which we will apply Proposition 9
By Lemma
for all f (f1 J2) e mm
(Ar)d(Y)f.))
Σ
v( ((a)))
(ii)
(Ji(i) - -2(i))²
22,
vii)
22,
((1) m())
47

---

applying Cauchy-Schwarz inequality. (())f2()))) s L, so we deduce
Assuming furthermore lIfll
we can bound
sup (A), 1-1-1
+ +
Zip(i)
$ K.
The above computation also shows that A is p.s.d., so Point (ii) of Proposition 9 yield that for all 0
applies to
IP Amia (O(Y) -t 2] (n m) exp
2x(t E [+]1))
By the Thorin interpolation theorem and duality ( |E [6]]
|Pll2.2 s |PI 1/2 |1
1/2 |
00,00 and using 57 and 558 we get finally
P[]
21 2/
z
sP
- | 10.00. 2/22 z
P
Amii - -E[o]) -t/2 z]
-t2
-t2
2m exp
(n+ m) exp
8Ni(+ + Pil 100000
8k(t+ 2 | 11
which yields the result, observing |M| 00,00 2
48

---

Extension to shifted successor measures and leave-one-out concentration
In this appendix we leverage the concentration for the empirical estimator P RR established in Theorem 8 to deduce concentration for more complex functionals of P. First we exploit linearity and contraction properties of the map P ~ Pr to obtaín concentration in spectral norm for the policy-evaluated matrix Pa Then we use simple identities to deduce concentration for the shifted successor measures M Finally we establish the technical concentration inequalities of Lemma
F.1
Contraction properties the map P PR
Given policy consider the following linear operator vectors:
K Ex
(59)
f - {s
Note that K be identified with S x X matrix, namely (= T(s,a)l so we can see that
Px PK
(60)
Given a probability measure on S, let us write x a the probability measure on X given by J x ( a) := (())=(s,a), Note any probability measure X has this form, т (Ts,-) is thus the law of the action conditional of the state.
Lemma 13. For all probability measure μ on S. policy n.
(i) |K =1,
(ii) (Kall) $
(ii) for all (8,0), (8',a) X, PT(5' (f
Here p is the adjoint of P as an operator (p)) (pxx)) while P is the adjoint of Px which is an operator (1 x π) e (4x T).
Proof. Let μ be probability measure S and a policy, Point (i) comes from the fact that K is stochastic matrix. Then by Jensens's 's inequality for all f I
| (
En(s) Σ [((
Σ (())=() -111(( (( (K,0)EX
which implies that | | (((N))) $ 1. Finally, by definition
pi ((s.))(
mIs')
(('')(s',a'')
(x
P (s' (s'',',s,,))
1X
and thus
pt
pt
00,00
00,00'
F.2
Extension to shifted successor measure: proof of Theorem 7
The concentration of shifted successor measures will be the consequence of deterministic mean- value like bound, itself consequence submultipliaatiiity and the following well-known identities: the telescopic sum formula
I 1=1
I 1=1
b =
Σ 1=1
I 1=1
(a, by)
π 1-f+1
by
(61)
49

---

and the resolvent identity:
a a1-b- = -50
(62)
Lemma 14. Let p a probability measure on [n]] and consider here |-|1l = I-lle()))) Let A, B
Rux with 1 6 [B] $ |AA,, 2 0,7 E [0, [A]]) and write ou (A) 47A)= Suppose
| B| min [BB] 1-1/B] ). Then
|B|
max (k: (1->|111-)
(A) ok [B)| (B)I
1.1 Bl|
1 |B|
Proof. First decomposing.
A (1- (I- (A* (1- 1* (1- (1
+ (A* -A* - -(--7B)
submultiplicativity of the spectral norm allows to bound
( & | B* |
+ B1
1|4 B B* | [[--
(63)
so it suffices essentially to consider the case of powers and successor measure separately. By the
telescopic sum formula (61)
$ ||| Σ
AA B&I
A - B
BI| k-v
F=1
[
|| - B
B
[A [8]
-1
Next we use that [B] s |A] with mean value inequality and the inequality 1 xr bound
1
|A|]
k-1
R:
A
[B]]
K-1
A - B
k 1 +
B
ke
(k-1) 1)
LA-B1 [s
Supposing now |A- B|| s |B]]
/k the exponential term is bounded by 3.
On the other hand the resolvent identity (62) implies
1 -1--1)--(11733
(1-
7 7A)
7 1|- B| [|[[[[[[]]]]]] -BB-1
7 7|1A B|
(1 (1-> (1- B| + B()))
Using the assumption that | B||
1->| |3|
the right hand side is bounded by
27 2-|4-81 (1~>1<1)"
Plugging
the previous bounds in (63) we deduce
3k |B|
IA
B
B|
AA
BI
64 ||]| k-1 ||A BI²
(A)), -o.- (0x,((B) (B) (B)
1 7 B1
(1- > B1)
(1 7 B1
B * ||A - B1
2
6d - B
3d +
7: |BI
1
7 B
1- |B]
which gives the result after using again ||A B
1-7| B|
50

---

Proof of Theorem 7 Let v be a probability measure on 2, which can always be written as p
for some probability measure μ on S and a policy x. Apply Theorem 8 to RR*S obtain
-t min minaa.)) (s.a)=s'
P PlP--Pleea,,ee
P
2
4n exp
((s.a)t((e) 8(1 2 P o0,
Then Point (iii) of Lemma
13 shows
| | = |
1 if v is supposed invariant. Then from (60)
and Point (ii) of the lemma
|P+ Pa P=lla = |IP - (0))))))))))
P-P (l) (K
P Ple
thus the concentration of P immediately transfers Ps. Finally we deduce the concentration of
Ma. from the deterministic bound of Lemma 14 Supposing invariant also implies ||P|
Thus for s if P Pl| 1/Ck.y $ 11CC,, the conditions Lemma 14 are satisfied, which
thus implies |Mx MR M s Ck,7 |P- Pl| < L. Therefore the events { { P- Pll 1/Ck,y) and
{|] Ma Ma.a 2 1) are disjoint.
F.3 Leave-one-out concentration
We now establish the technical concentration inequalities of Lemma The proof strategy is similar to that of Theorem 7 we first establish concentration for linear functional of P in the following proposition, combine them with the contraction properties of Lemma and the identities (61)
and 662.
Proposition 10. Consider the same setting as in Theorem Let A mxxx and let p be a probability measure [p]. For all I E [m], and t 2
(i) P
A 2t (Y:) (p+ 1) exp
-z
21
(i) P P PAAA-PAlean P 21] n(p 1)exp
-f
21A1:2000
Proof. For (i), fix L [n] and ((Y) A 1xp, Since reason conditional on (Yi)).s,, is in fact here a function of the multinomial variable (Yız).<(m) only, so Proposition applics with a.s., and N replaced with Z₁ here. We can then bound
A |A(J,))lE
|Ale
7
72
Zi
so applying the point (i) of Proposition gives (i). For (ii), noting that |Ta - pd A Allep()
maxiq[]] (P(I.)) P(L.) 1eeep suffices to prove concentration of the latter row matrix for
fixed 1, which can be done above, and use union bound argument. The only difference lies in that we do not reason conditional on (Y:) anymore, so now we bound
Ey, [IAnJóle
1
Σ (1
N
[J][m]
1 Σ
P(i,))
1i-1 (AA())))))
Z:
A ((())) AAPer
S
NZi NZmin
and similarly for Er, () Applying point (i) of Proposition gives (ii).
51

---

However for Proof of Lemma 7 We first by claim that the result of Proposition place of P and P. The latter proved two inequalities of the form P'
10 also applies with Pr. Pm in
[PP - P)A 2 8) fi(1lA12,,0))
where Jt is a non-decreasing function. From (60) we can bound
P [[[ Pa) 2 t) = P [[] , 2t]
$ A1(()K77122...))))
$ [(( Kalloo,0
|| 1
ft((1AA) 2,00
using the fact that ft is non-decreasing and Point (i) of Lemma 13 This proves the claim. We will
thus apply Proposition a0 if it applied directly to P.,. For simplicity omit the subscript for the rest of the proof, writing P in place of Pm-
The proof of 24 is similar to that of Theorem
8 For other points, we also start by decomposing
Mr,
1 A [Pt
(I (I (1- (F()) (F())* (I- (I - A
+
(64)
Let B = (I (I- A. By the telescopic sum formula (61) the first term can be bounded
p P1.
(p)) (p)
- (P-
as (P) ) ( jif I. Now observe the matrix ( B is independent of Yy, so by point (i) of Proposition 10 and union bound the probability conditional on (Y,)iw that one norm factor in
-t2
the above sum is larger than is at most k(p+ 1) max exp 2|((8 B lam.
all i é [A:]
(1A1
(((()) (ll0))-Blle $ (1- -1 1
1 1-7
as (1- - (P())) -1 is stochastic matrix. Bounding also eventually that
[ get
-P(1 -111-))22
[[I[[s((.)) (L.)) 2
1) exp s k(p [
2h |A| |A(12(0).
For the second term of (64). the resolvent identity
62
gives
[(P()) ((I->)) - (1-)P())11 (](,-)) = (()) ) (I -
(1,))
< IP-- (l.))
Thus with the same arguments as above point (i) of Proposition 10 shows
-t2 (1(1-))21
(1.-) 2 (Y.) (p+ 1) exp
2 2||A|1 2
2,00
Finally the third term of 644 can be bounded as
|[[ | - ( (1, (1- All
= ([p (1)))) p()) (1,))B]
$ 2 |(P (ipp-p())( (1.))()))
1-7
52

---

and is thus controlled as the second term. Combining all three bounds yields 21
The proof of (22 follows similar arguments, using point( ii) of Proposition 10 instead.
Finally for inequality (23) the proof is almost the same except there is no mul- tiplication by 1 on the left, so the factors (I,)(,, (1))) and (B0)_(())) (1,2) need to be replaced with (.1) ews || (1-)) (11) (m))) and (
(:D)lesss (: respectively. We
bound these terms as
(-D)())) = p 1 11 (m)) $
=|Pii1e lew), | || lews, Vu(1) (1- (( (1 (00) Vi(1)
and (100--(00))00~>>>-10000 (I (())))())))))
+ (I- (ws)))))))) Vi(I)
Suppose now that the terms of the right-hand side concentrate: then for some constant C > 0, using that v is invariant we would get ||Pi| (e)) C | (w) C for all i é [k]]
(1 7). Then on this event reiterating the above argument would eventually give the bounds
C ->))))) C'
C/(1->) and |P* |aw $ C/(1- -
| -
- ( (()) $ SCVu(1)bL,
CVv(T)t (1-7)²
((()))
((T [(T-T))+
-I (I- All (e)
20 2CV/(TTtt
- 1 [All)
-
-11-7((0)-1
(1-7)²
-(1--))22
with probability at least 1 - (k+ () (pp+11 exp and thus also unconditional. We then deduce
exp
conditional on (Y, iml
2max((((1->)11) 1
-122
P [[] M - 17.22 n. All (e())))))))))
s (k+ 10)++1exx exp
202, v(1 |A|))
IP
Bie [b]] : p | (12 cc]
IP (p(t)) (1- (2)))))))))) Cc((1
IP
(1 ( C/(1-))
The three remaining terms can be controlled by Theorem 7 and (24). which gives the second term in 23 We omit the details.
53

---

G Local mixing phenomena
In this appendix we prove the results of Section 5 We start by proving Proposition I in $G.1 In
G..2 we explain how bounding the spectral recoverabilty reduces to bounding the 2 co norm, at least for normal chains. Then in $G.3 we give detailed background on functional inequalities for Markov chains and explain how our results differ from the classical analysis of mixing times. Finally, 4 and Proposition 2
in GG.4
we extend these inequalities and prove Theorems
G.1 Singular value bound: proof of Proposition
Proposition D will be straightforward application of the following, more general result. Here we consider the norms, singular values, etc. be defined w.r.t. any probability measure.
Proposition 11. Let A R=xm For all y (0, || 1222), 0, i [n]]
(A(A))
(AA))
S So, (A=
(65)
1 1+7 + 2.2
1 ||A
Consequently
( Σ < F26
|| 1
(66)
+ ///>||Ag ||
2,00
Proof. Using the classical inequality for singular values o, (A)o, s (AB) (A)o,, (see e.g. (27) valid for all matrices A, B and i, we get
- (,((T->4)=)o;;(
(4 (T=))))))))) sa <((->>)))))
Now simply notice 01 ((1 - - - (-4--A)-110 11,,2 $ 5(1 - (1-771 | 2 |I A112, 111+7 || hence
and 01 (1 7A)
1
on ((1-7))-)) 0. a1
1 |Al22
Summing over i and using 13 yields
2 ||A*|
Σ 12R
Σ Et'A' A
1+> |All
2,00
126
Proof of Proposition ! Apply the previous Proposition with A P, and note that if the underlying
probability measure is invariant then | 12.2
G.2 Spectral recoverability for chains with normal transition matrices
From Definition
3 and for any matrix A with SVD A = UEVt, we can express {(A)
|||| 1/212 where the absolute square root is defined by |A| |A| : UE!/ When A = p2k is an 2,00
even power of P. it is thus tempting to try relating ((P2k) with ||P0122.0
2,00 However we do not know
how to achieve this, as the singular vectors p& and p2k may be very different. A case where this is possible is when we assume the chain to be reversible more generally normal (12). in the sense that PP pt P. By the spectral theorem, such matrices are diagonalizable in orthonormal basis, making the singular vectors coincide with eigenvectors.
Lemma 15. Suppose PP' = P. Then for all k 2 0.
E(P2N) < | 2,00
Similarty {(Ma)) (1-~y1, (1- |M 2,200 where recall Mj := (1I
- -PP)-
54

---

Proof. Let P== E, onioo be the SVD of P. By normality and the spectral theorem, the singular vectors coincide with eigenvectors, so the SVD of ph is p =E. of uho for all A 2 O. Consequently
{(P2k) max Σ (P wh. max DaaxE,, (
p+1 2,00
For the shifted successor measure, the singular values of M2 are of (1 -0,,) hence
<(M2x) -max Eo,((t))( (x))
$ (P))) mmxx (Pt((1
(11- ph pm112.00
We leave as an open problem the question of how to extend this result to non-normal chains, but consider it as heuristic proof that having <(P*) bounded should in general be essentially the same as having 2,50 bounded, up to multiplying k by 2.
pk] |
G.3 Functional inequalities for Markov chains
From now on, we consider RRax to the transition matrix of an irreducible Markov chain with invariant measure v. Using the framework of A. the underlying measure will here be until further notice.
Identifying v with row vector, the rank one matrix 1v is the matrix of the chain at stationarity,
and it is readily seen from (TT) that |r - 10 2.00 = || ||,
2,00 - 1. It makes sense to define the
fe-mixing time as (2(E) = inf(! 2 0: pt 1u/12 $ se), which may be infinite. We also write
E, [f] = E (x) and Var, E, [}]] E, [f]
Recall the definition of the Dirichlet form
Epr ((T- ((T-
(67)
Remark 1. We consider the Dirichlet form of the multiplicative reversibilization PP", which appears naturally when working with discrete-time Markov chains (22). The arguments that follow also extend, and in fact are simpler, for continuous-time Markov chains, for which we directly work with P. We refer to (49) for a comprehensive reference. It is also possible to reduce to considerations on P only with laziness, i.c. if the chain has uniformly lower bounded probability to stay put. If P(x, x) a for all x E [n:]. (49 Equation (1.12)) shows that Epp 2 (fEr(f,f).
The argument behind the use of functional inequalities is as follows: by duality ()) ||' 2,,00 [[("")"] su l
(P*) flly. Therefore it suffices to bound [(*))* for all f R". Now
for fixed f, it is easy to compute
(('') -| EEPP ((pt-()t ((p=)))([[==<ppp((()))) (p'--)))
(68)
(This is really discrete counterpart of differentiating || fl,)). The goal of using functional
inequalities is thus obtain lower bound pp,((g F(1g1>) valid for all y such that |g]|| 1, that can be "integrated" to get estimates pt fP1 and eventually on |P*|| The most classical inequalities are Poincaré (22), log-Sobolev (16) and Nash inequalities (17). to which we can also add the spectral profile technique, which stems from Faber-Krahn inequalities (24). We focus in this paper on Poincaré, which are the simplest to establish, and Nash inequalities, which served as our main inspiration and can prove complementary to Poincaré inequalities.
55

---

Poincaré inequality: the classical Poincaré inequality takes the form
v VR=::
I
(f) & (J.J),
(69)
for some constant À 0. Plugged in (68) and applying the above argument, it implies the decay rate
| 1 $ (1- (1 min (see Corollary 1.14 of (49)). This gives in particular bound on the
mixing time:
(2()) s x
log(umin
(70)
For our purpose of applying Theorem 1 we do not require that strong mixing estimates: we could be content with || 2, = (1), which could occur on time scales much smaller than the mixing time. The Nash inequalities of (17) were introduced precisely to get such decay rates, when the Poincaré inequality alone is not sharp. Nash inequalities are however notoriously difficult to establish.
Nash inequalities: in view of (54), distinguish two types of Nash incqualities, which we call type and type
Type I reads
(a) 1 s (I:
(71)
for some constants C, 0. Plugged in (68) and applying Lemma 3.1 of (17) yields the bound
d/2
|
Lu 1,
C(1 + [d])
2,00
k+1
which in turn gives the mixing time bound (E)
c(++4))
Using Jensen's ' inequality, we also see that (71) implies a Poincaré inequality Var s CEr(S, f)- Thus Nash inequality can be combined used in place of the Poincaré inequality to get rid of the log(umLt) factor in (70). This is generally sharp for "low- dimensional chains" like random walk on grids, where the constant that appears in the Nash inequality coincides with the dimension parameter.
Type II has the form
| 1 2(2+2/d) s sc (E. 1 T 11 1511
(72)
for some constant C, 0. Theorem 3.1 and Remark 3.1 of (17) show that this implies the decay
| 1,00 (C(1+ [d])
4/2
Vk [0,T]:
k ++1
Unlike the type inequality, (72 implies no Poincaré inequality and no mixing time estimate. Note also that by moving the expectation term of Var,(f) to the right hand side, type I inequality 7 implies a type II inequality with slightly worse constant C and 1/C.
G.4 Type Poincaré inequalities and applications
G.4.1 Proofs of Theorems and and 3
As seen above, Nash inequalities, when they can be established at all, provide only a polynomial decay of the 2- oo norm. obtain an exponential decay, we consider extending Poincaré inequalities instead. The clear analogy between (7T) and (69) motivated us to develop analogous "type II" versions of the Poincaré inequality, that incorporate an additive é term. This is exactly the result of Theorem 2. which we now prove.
Proof of Theurem 2 We use the argument sketched the previous section. Let f R such that ( sll, [[(Pt))]] ||f however by duality (9)
|f 1 and set u4 || [((t) f| Note that || [[(P))
|P || = 1. Thus ( fll, 1 for all 2 Consequently, the type II inequality 5
plugged in 68 yields
Ut U411 S -X XC
56

---

which in turn gives = (P*) )"ff( fll2 2 (m - (C) C' by an easy induction. Then remark that uo = 1/l Viin |/ V'iin Since this is valid for all f such that |/ 1 we deduce ((t))) ||,, 12 s (1 (v - CC
Remark 2. The same arguments could be applied by exchanging P and P to give similar bound for (P*)* as is required for Theorem There is one difference however in that we need the invariance of v to have | 100,00 =1.
Proof of Theorem Let f E IR" and write f. := U,U,F f for its projection onto the r first singular vectors. Note that Erm (f fr fr) and hence
Epp ff. pp (tr. (f- f+).
If the underlying measure is invariant, ppt is a stochastic matrix Lemma 12 implies that /-Ppi
0 and thus Epp (J,J) 2 pp S fr). Thus the Courant-Fischer theorem (27) Theorem
3.1.2) gives
Ar+1 Ilf - frll Epp SJ-Jr.J =fp
where we write Ar+1 -- On the other hand use Hölder's inequality to bound
1/1/2 (s fr, (G, s |/ 1/122//12 + 1s l/
Observe then that
l1f+ = U,U 1U+12,00 Iflla
so after simplifying by 11fl we deduce
X |1 s Epp (f, 1/2 |U 1fll
Using b)+ b²) we finally get
Art1 151 Eppt (f.f) A,11 11,12, |fl
G.4.2 Combining inequalities of induced chains
In (17), Diaconis and Saloff-Coste showed how to establish type Nash inequalities from local Poincaré inequalities. This suggested that type II inequalities are related to local notion of mixing, which we establish formally in Proposition Given the definition induced chains (Definition 4 is immediate that for all fER" R"
Eu, (S, Ev ( (f.
(73)
ps f(s ((5') Euge, Pec ((ss,,(s=))
On the other hand it is also straightforward that || (e)(2)) (SS) J|s P for all p oo). Our decomposition result is based on these two simple facts.
(we))) + +(( lis=
l(e(vs)))
Proof of Proposition
The result is a consequence of the following inequalities:
l = +*(S") fist 112 (ve))
s sr(s) A5 Ev (fss + Cs (isl
+ +*(59) X5d Pso (fise: fis-)
+ Cs [ise 2
(2(())))
minn(Assss-) - Eu,P(, max
Cs Cs.
(11is + (1
u(S) u(Se)
s min(As, As=) -E, max
((S)' u(Se) |
Cs Cs:
57

---

The equality uses that S. are disjoint, the first inequality comes from applying the Poincaré inequal- ities, the second uses (73) and v(S) fisile(us) = [[fisllete) the last inequality is a consequence of a² + 12 & (a + b)² for a.b20. 0.
Cerooiitioo@rquirrr functional inequalities for induced chains, with respect to the induced measures. It is wrong in general that the induced measures invariant for the induced chains, but it is true for reversible chains (34). For completeness, we prove in the following Lemma, to justify the consideration of induced chains with induced measures. We recall a chain is reversible if it satisfies the detailed balance equation, which translates matricially into P P.
Lemma 16. Suppose a reversible Markov chain on [n]] with invariant measure v. Then for all subset S = [n]] the restriction v to S is invariant for the induced chain Ps.
Proof. P is reversible if and only if it satisfies the detailed balanced equation ((x:)((s.))) ((,,) for all v. y e [n]] Taking the induced chain on S does not affect the transition probabili- ties between x y in so the equation still holds for the induced chain and the measure induced by v.
P(r, y)
G.4.3 The 4-room examples: proof of Theorem
We now proceed to prove the bounds for the 4-room environment of Theorem
Proof of Theorem 4 a random walk on a graph P reversible with invariant measure being given by v(x)= deg(2) v Ey deg(y), where deg(z) denotes the degree of x. Thus we need to consider the Dirichlet form of PP = p2_ The latter is also reversible hence by Lemma 16 are all induced chains (P2) with the induced measures as invariant measures. Now for each i E [4], (P2) )iG,
satisfies type II Poincaré inequality: namely for all f R...
A ()lle s ((P)),, (J,f) + >u I1llee
with A; 1011-2((P"))ep ((P))) Sourant-Fischer theorem as for Theorem 3 whole chain satisfies
)c:) ) the spectral gap of the p.s.d. matrix (P*) This consequence of the
It is thus a simple application of Proposition that the
1-A
(1- (1-A)II((eo) S E (f.f)+
min, v(V)) 1
with X == min, Ar which by Theorem 2 limpiie the decay rate
| 2.00 s (1
A) Vmin + min; v(V))
This proves the first part of the theorem.
For the second part, suppose that min; ((G,) Then for 1 X-1 log(y |P'
min e we obtain
2,00 S c_l. Since the chain is reversible we can use Lemma 15 to bound the spectral
recoverability as well and get {(P2) s s ! Then Lemma shows that p2r [ for the smallest r such that 0 (p2)) S (c +e). We claim that:
]r |r 12, se
(p(2))) s (1 X)", for all 0.
(74)
Provided the claim holds, this implies that as (0:0(:p)))) (P4)) s <e- 2ht v 22 by the choice if
Let us prove the claim (74 Note that by reversibility as (P2)) = 03 ( so it suffices to prove that 1 o (P2) 2 A. From the Courant-Fisched theorem:
{p=
1 (P2)=
sup
inf
codim W=4 feW
1/1
f=0
58

---

Let W be the subspace orthogonal to the subspace Span (1a,, é [4]) spanned by the indicator of each subgraph. It has codimension we can lower bound
g (f,
inf
feW
lfll
f+0
for this particular subspace. Now decompose / Σi= SiG.- As in 73
we can lower bound
(f=(f.f)= = Σ r (G;) (P2))a, (hanfa)
Now observe that for each i, since (S. (/c, la.) 0 f W, we can lower bound
(r=) (fa. A | ((aaalll
Therefore
fp(f.f) 2 Σ [AM(G))ffa 6-1
2 A 21
which proves the claim.
Remark 3. We note that Theorem i quite general and applies to arbitrary decompositions of the state space. However, our framework particularly effective in scenarios where there is significant gap between the global mixing time of the Markov chain and the local mixing time within each "room." " In favorable cases-such be substantial. In contrast, if each room is 2D grid with n² states and the policy corresponds random walk, the local mixing time scales O(n2). while the global mixing time scales as O(n" logn). This setup closely resembles the so-called "n-dog" graph studied in Example 3.3.5 of (54), where two n grids are connected at a single corner. In this case, the difference between local and global mixing is relatively mild. Nonetheless, in our numerical experiments, which include scenarios resembling this more challenging setting, we already observe significant gains from shifting the successor measure.
when each room is an expander graph this difference can
59

---

H Further Numerical Experiments
To complement the theoretical insights and main experimental findings, we provide additional numerical results that investigate the behavior of shifted successor measures across a wider range of settings. These experiments aim to probe the robustness and generality of approach in different environments, under different data collection policies, and with both model-based and model-free estimators. All experiments were run on single CPU and are reproducible within day. As SM
mentioned in the main text, all code is available at htttts://githeii com/
H.1 The 4-room environment
We now revisit the 4-room environment theoretically analyzed in Theorem 4 where the state space is partitioned into four well-connected regions (rooms) linked by narrow passageways. As discussed in the main text, this structure induces metastable behavior: the chain mixes rapidly within each room, while transitions between rooms are relatively infrequent. In this section, we additionally make the Markov chain aperiodic by allowing the agent remain in its current state with probability 0.1.
Figure 6 illustrates several empirical findings. On the left, we show the 15x15 discretization of in this section. In the center panel, plot the singular values of the shifted successor measures M for various values of the shift h. As theoretically predicted. increasing & leads to sharper spectral decay, indicating stronger low-rank structure. Notably, for higher shifts when all states within a room are reachable the effective rank is close to 4, matching the number of rooms.
the 4-room domain that
1.0
M Maalllas
10
pp
0.5
10
10
20
index
shift &
Figure 6: Left: 4-room environment with 15x15 discrete space; Center: singular values of shifted successor measures Ma,e & for various shifts & (uniform policy æ, discount factor = 0.97); Right: entrywise norm differences between pk and its rank-4 approximation (blue circles), and between Mr,k and its rank-4 approximation (red squares). As in Figure 2 which coincides with the norm in Section 3.2 up to / multiplicative factor under the uniform measure v.
the standard || 1,,00 norm,
On the right, we plot two metrics as a function of k: the entry-wise norms | [412,00 and |M (MM,,aalla,, Both metrics decay rapidly with k consistent with the bounds in Theorem 4 The behavior confirms that moderate values of (c.g., k = 4 10) are sufficient to approximate pe with rank-4 matrix. While such representation may suffice for navigating between rooms, accurately reaching specific target states within a room may require a higher-rank approximation. Nevertheless, shifting the successor measure consistently improves the learnability of low-rank representations.
These results validate theoretical predictions in structured setting and demonstrate how temporal shifting can uncover the environment's block structure. We next turn to more complex and less regular domains.
H.2 Additional Navigation Tasks
We now extend the results from Section additional environments increasing complexity. Specifically, we evaluate the impact of shifting and low-rank approximation of successor measures in two additional mazes: the U-maze and the Large-maze. All three mazes are discretized versions of the Maze2D environments from (23).
60

---

Here we repeat the setup from Section 6 and provide additional details. Unless stated otherwise (as in Section H.3), all data is collected using uniformly random policy. This simplifies the estimation process: under uniform data distribution, the invariant measure is uniform, and thus the measure- dependent norms introduced Section 3.2 reduce to their standard variants. In particular, the |2. norm and the singular value decomposition (SVD) used for low-rank approximation become standard.
Once the successor measures M are estimated, we evaluate policies that act greedily with respect to them. More specifically, given current state and goal g. the policy selects actions according to: argmax ΣλeA Mr,((ss a, g. b). as described in Section 6 the low-rank setting, the same greedy procedure is applied to the rank-r approximation [M To quantify goal-reaching performance and evaluate the obtained policy, we report two metrics: accuracy. the probability of reaching the exact goal (from random initial state), and relaxed accuracy, the probability of reaching any state within two steps the goal.
Figures annd the structure of Figure in the main paper. In each case, we compare unshifted and shifted successor measures across several metrics: spectrum decay (panel b), goal-reaching accuracy using ground-truth successor measures (panels c-d), performance of TD-learned measures (panels e-f), and sample efficiency function of dataset size (panels g-h).
(c)
(+)
accuracy
0.5
0.0
100
0.0
30
10
1.0
relaxed accuracy
(4)
[4]
(h)
0.2
01.5
0.5
())
1
10-1
100
130
index
rank
rank
number trajectories
I-shift
Figure 7: Successor measure analysis in the U-maze environment with 0.98 and uniformly random policy TD estimates use 10k trajectories of length H 100; rank is fixed 40 in (g-h) Results are averaged over 5 seeds and 100 random goals and initial positions.
(a)
(c)
accuracy
0.5
0.0
20
10
125
170
102
1.0
0.2
0.4
0.6
relaxed accuracy
[-]]
(1)
(h)
((MMaa)
0.5m
10-2
.0
75
125
150
175
0.0
50
110
index
rank
rank
number trajectories
iushift
Figure 8: Same setup as in Figure 7, now for the Large-maze environment. Rank is fixed to 60 in (g-h). All results averaged over seeds and 100 random goals and initial positions.
In both environments, we observe a consistent pattern: shifting enhances spectral decay (Figure and 8D), making the structure more amenable to low-rank approximation. When true successor
61

---

measures are available (panels c-d), moderate shift values yield better planning performance at low ranks, consistent with our observations the Medium-min maze environment. However, beyond certain point, excessive shifting discards too much information, leading to worse performance. This effect more pronounced when successor measures are learned (panels e-f), likely due to compounding estimation error over long horizons.
Finally, evaluate how accuracy varies with the number of trajectories (panels g-h). As in the main experiments, moderate shifts (A: = 3 or A = 5) often strike the best balance between representational power and sample efficiency. The trade-off seen in Figure g g- where small shifts underexploit structure and large shifts overburden estimation, persists across these environments.
Overall, these experiments reinforce findings from Section 6 and demonstrate the robustness of temporal shifting across domains. Even in larger and more complex mazes, appropriately calibrated shifting enables compact representations, improves planning accuracy, and enhances sample efficiency.
H.3 Non-uniform Data Collecting Policy
In contrast to the previous experiments that used uniformly random data-collection policy, now evaluate a mixed policy composed of 80% uniformly random actions and 20% averaged goal- conditioned behavior. Specifically, the latter operates by sampling a goal uniformly at random and following the optimal policy to reach it, repeating this process for all goals (corresponding to TD TD (als) = [s Fg o (cls)dpp (g) from Section with uniform PD). As shown in the leftmost panel of Figure 9 this results in a non-uniform invariant measure v. with states near the geometric center of the maze being visited more frequently.
1.0
shift A
accuracy
0.6
0.01
measure
0.4
6
0.0
300
(8,0) a) index
rank
rank
Figure 9: Left: invariant measure y with respect to M,. dashed line represents uniform distribution. Center/right: accuracy vs. rank for standard SVD and v-SVD, same setting as in Figure 4e), with only the data-collection policy modified.
To account for this skewed distribution, we use the μ-
weighted SVD (as described in Section 3.2) when comput- ing low-rank approximations of M Figure I0 shows that the reconstructions obtained with F-VV differ signif- icantly from those of the standard SVD, especially at low ranks. However, despite this discrepancy, goal-reaching performance remains nearly unchanged, as seen in the
25%
shift
20%
[[Ma)-MMabl
15%
10%
5%
center and right panels of Figure 9
0%
75
100
All experiments were performed in the Medium maze using the same setting in Section Interestingly, the results suggest that the uniformly random policy actually yields slightly better performance low ranks (compare with Figure suggesting that more uniform exploration may facilitate learning better goal-reaching representations.
rank
Figure 10: Relative Frobenius differ- ence between rank-r approximations of M using standard SVD vs. v-VV
H.4 Model-Based Estimation of Shifted Successor Measures
We now compare -eiforel-difference (TD) learning with a simple model-based (MB) approach for estimating shifted successor measures. In the model-based case, first estimate the transition matrix
62

---

Px from data, and then compute the shifted successor measure Mr.k Ei-o Y p using truncated power series expansion. Figure II (left) reproduces the TD-based results from Figure (g) in the Medium-maze, while Figure (right) shows the corresponding performance of the model-based estimator.
1.0
accuney
0.6
k
1 17
0.00
10
10P
10"
number of trajectories
number of trajectories
Figure 11: Goal-reaching accuracy in the Medium- maze using TD (left) and model-based (right) estimation. In both cases, use trajectories of length 100, collected with uniformly random policy, y = 0.95 and fixed rank r= 40.
We observe that the model-based approach maintains higher goal-reaching accuracy even for larger shift values k. This is expected: unlike TD, which relies on sparse, temporally aligned supervision observing specific (st, at, St+k-1) transitions), the model-based method can leverage all available transitions to estimate P=, making it less sensitive to the horizon length. In particular, long-range transitions needed for higher shifts are harder to estimate via TD when data is limited, whereas they are implicitly captured P= and recovered through matrix powers in the MB estimator.
While model-based estimation proves more robust in this tabular setting, it does not easily scale to environments with large or continuous state spaces. Storing and computing with full transition matrices becomes infeasible, making function approximation challenging. In such cases, TD learning might be more practical and scalable despite its limitations with longer shifts.
H.5 Extension the Non-Tabular Setting
A natural question is whether the benefits of shifted successor measures observed in discrete maze environments carry over more complex settings with stochastic dynamics and continuous state- action spaces. We believe that learning shifted successor measures may yield similar benefits in such environments particularly cases where learning the standard, non-shifted successor measure proves challenging.
While we do not provide formal guarantees under function approximation, we believe similar effects are likely to emerge in practice. This intuition aligns with prior work on hicrarchical reinforcement learning (ex. (50) (T)), where high-level policies capture the coarse structure of the task and steer the agent toward the vicinity of its goal. It would be interesting to explore whether shifted successor measures could similarly encode such bigh-level behaviors.
One particularly promising direction contrastive learning. For example, (1 samples positive ex- amples from geometrically distributed time offset governed by the discount factor 7. To incorporate a shift k one could instead sample the offset from Geom (1-)) -)++ + k, effectively biasing learning toward more temporally distant predictions.
By contrast, extending these ideas to Forward-Backwart Backward (FB) algorithm of (63) is less straightforward. A key strength of FB is its ability to learn from one-step transitions (st, ar St+ ) independently of the data collection policy. How to integrate a meaningful notion of temporal shift into such a framework remains an open and intriguing challenge.
We see these directions as promising opportunities extend the benefits of temporal shifting beyond tabular settings, and hope that the theoretical insights in this work will help guide future progress in more realistic domains.
63


Reviews:
[{"review_id": "Nql6zhUGzX", "reviewer": "Reviewer_FgQx", "summary": "The paper studies the low-rank representations in RL through a shifted successor measure, supported by strong theoretical contributions. It claims that the standard successor measure is not inherently low-rank, and a shifted successor measure, which captures dynamics subsequent to omitting earlier transitions, can demonstrate the low-rank property. This paper provides a novel perspective on the analysis of long-term dynamics. However, the proposed method may lose practicality since the assumptions in Section 5 are somewhat strong, which may fail in practice (e.g., in complex or dynamic environments).", "questions": "- How to choose k in practical implementation?\n- The proposed method may lose practicality since the assumptions in Section 5 are somewhat strong, which may fail in practice (e.g., in complex or dynamic environments). In addition, the experiments validate the results in a small, discrete envs. Demonstrating the method's effectiveness on a more challenging, high-dimensional benchmark would be better to show its practical values in real-world tasks.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "# Strengths:\n- Novel Perspective: The authors redefine the low-rank assumptions in RL by introducing the shifted successor measure, providing a novel perspective on the analysis of long-term dynamics.\n- Theoretical Proof: The authors provide rigorous proofs with spectral recoverability and Type II Poincaré inequalities to enhance the understanding and effectiveness of low-rank approximations in RL.\n\n# Limitations:\n- Selection of the Shift Parameter: The theoretical results explain why a  shifted successor helps, but without a guidance to choose k, which is critical in practical implementation.\n- Strong Assumptions: the proposed method may lose practicality since the assumptions in Section 5 are somewhat strong, which may fail in practice (e.g., in complex or dynamic environments). In addition, the experiments validate the results in a small, discrete envs. Demonstrating the method's effectiveness on a more challenging, high-dimensional benchmark would be better to show its practical values in real-world tasks.", "was_revised": true, "final_justification": "Thanks for the responses of the authors, as they addressed many of my concerns.", "rebuttal": "Thank you for reviewing our paper. Before answering your questions, we would like to briefly highlight our contributions.\n\nOur main contribution is to identify conditions under which low-rank structure naturally emerges in zero-shot reinforcement learning. Unlike prior work that assumes universal low-dimensional representations that generalize\n    across tasks, e.g. Forward-Backward model (Touati and Ollivier, 2021; Touati et al., 2023) or goal-conditioned RL frameworks (Andrychowicz et al., 2017; Eysenbach et al., 2022b), we provide a theoretical basis for when and why such structure arises. \n\nSpecifically, we show that learning successor measures directly is statistically challenging, and demonstrate that a simple temporal shift of successor measures naturally induces low-dimensional representations. \n\nFurthermore, we present preliminary numerical results in section 6 and additional experiments in Appendix H that illustrate the benefits of learning shifted successor measures. We believe that our work lays the foundation for practical algorithms for policy learning via shifted successor measures.\n\n\n**Choosing the shift parameter $k$ in practice.**\n\nAs discussed in section 5, the optimal shift value $k$ can be derived in certain settings. For general environments with complex dynamics, $k$ must be treated as a tunable hyperparameter. Its value is related to other hyperparameters, such as the discount factor. This is consistent with prior work - for instance, HIQL (Park et al., 2024) treats the number of subgoal steps $k$ as a hyperparameter, tuning it per environment. We argue that selecting shift parameter $k$ in our setting is no more difficult than setting the subgoal step parameter in HIQL.\n\n**Practicality of the assumptions in section 5.**\n\nAs far as we are aware, we are first to analyze what happens when shifting successor measures, and we believe this idea is novel and interesting for further practical analysis. Our main result of section 4 makes no assumption and applies to arbitrarily complex, discrete dynamics. It could be extended to continuous settings, with the right regularity assumptions, as we answered Reviewer tYCN. The ideas of section 5 are also universal: mixing phenomena exist beyond discrete Markov chains, which is mainly a way to avoid more tedious formalism in continuous setting. Furthermore, these ideas could apply even to Markov processes which do not mix in the classical sense. We discuss some extensions in Appendix C.1. Thus we believe our analysis holds in good generality and provides insight that might be interesting for their own sake. What we do in section 5.2 (decomposable Markov chains) is to just provide an example where the analysis can be directly applied. There, we indeed make some assumptions.\n\n**On the scope and complexity of experimental validation.**\n\nAs noted in the main text, Appendix H provides additional results on goal-conditioned tasks, which are discretized versions of standard (continuous) benchmarks for navigation tasks. There, we also discussed the impact of different data-collection policies and learning algorithms. Moreover, Appendix H.5 discusses extensions to non-tabular environments.\n\nWe agree that evaluating on high-dimensional environments is a valuable future direction. However, the goal of our experiments is to validate the theoretical insights under controlled conditions, where factors can be isolated and analyzed rigorously. We believe the current experiments, together with our theoretical contributions, make the paper comprehensive and self-contained."}, {"review_id": "gyy8OMSwtn", "reviewer": "Reviewer_xQzx", "summary": "This paper proposes ​shift successor measures​ to better separate two types of transitions: those involving short-range dynamics (which remain inherently high-rank) from those governed by long-range interactions. The experiments demonstrate that shifted successor measures admit more accurate low-rank SVD approximations than non-shifted counterparts, and that enhanced representation yields consistent performance gains in goal-conditioned reinforcement learning tasks.", "questions": "1. What's the computational efficiency of deriving the shifted successor measure estimator?", "limitations": "Yes, the author presents the discussion on limitations in the appendix.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Pros:**\n\nWhile I'm not familiar in low-rank RL theory, the paper demonstrate its contributions to this research area. It clearly introduces the problem setting in the introduction, followed by explanations of the methodology grounded in strong intuition that build toward a rigorous theoretical analysis with detailed proofs. Critically, the empirical validation demonstrates that shifted successor measures achieve notably better low-rank approximations than standard counterparts, confirming the method's effectiveness.\n\n**Cons:**\n1. Experiments are confined to a ​single discrete environment​. Broader validation on a continuous environment would be better to support claims of general applicability.\n\n2. Adding comparisons against baselines would better demonstrate the advantages of the proposed method.", "was_revised": true, "final_justification": "As indicated in my prior comments, while my expertise is less aligned with this particular paper's specific scope, the contributions described lead me to uphold my original decision.", "rebuttal": "Thank you for reviewing our paper. Before answering your questions, we would like to briefly highlight our contributions.\n\nOur main contribution is to identify conditions under which low-rank structure naturally emerges in zero-shot reinforcement learning. Unlike prior work that assumes universal low-dimensional representations that generalize across tasks, e.g. Forward-Backward model (Touati and Ollivier, 2021; Touati et al., 2023) or goal-conditioned RL frameworks (Andrychowicz et al., 2017; Eysenbach et al., 2022b), we provide a theoretical basis for when and why such structure arises. \n\nSpecifically, we show that learning successor measures directly is statistically challenging, and demonstrate that a simple temporal shift of successor measures naturally induces low-dimensional representations. \n\nFurthermore, we present preliminary numerical results in section 6 and additional experiments in Appendix H that illustrate the benefits of learning shifted successor measures. We believe that our work lays the foundation for practical algorithms for policy learning via shifted successor measures.\n\n**On the scope and complexity of experimental validation.**\n        \nAs noted in the main text, Appendix H provides additional results on goal-conditioned tasks, which are discretized versions of standard (continuous) benchmarks for navigation tasks. There, we also discussed the impact of different data-collection policies and learning algorithms. Moreover, Appendix H.5 discusses extensions to non-tabular environments.\n        \nWe agree that evaluating on high-dimensional environments is a valuable future direction. However, the goal of our experiments is to validate the theoretical insights under controlled conditions, where factors can be isolated and analyzed rigorously. We believe the current experiments, together with our theoretical contributions, make the paper comprehensive and self-contained.\n\n\n**Comparison with the baselines.**\n        \nThis paper introduces a novel insight not previously reported - assuming low-dimensional successor representations apriori is unnecessary, as low-dimensional structure naturally emerges when shifting successor measures. We believe this theoretical contribution is significant on its own and can lead to further advances.\n        \nOur algorithm is not directly comparable to standard baselines because it relies on SVD-based estimators, which are tailored to the tabular setting and do not trivially extend to high-dimensional environments. As discussed in Appendix H.5, extending the approach is possible but would likely come at the cost of the theoretical guarantees established in this work.\n        \nFinally, our experiments are designed to illustrate and validate the theoretical results in a controlled setting rather than to benchmark against existing methods, ensuring a clear link between theory and empirical results. \n\n**On the computational efficiency of shifted estimator.**\n\nIn the tabular setting, the computational complexity of our algorithm is dominated by the singular value decomposition step. For more general settings discussed in Appendix H.5, the efficiency depends on the underlying algorithm for learning the successor measure. In some cases, such as when using contrastive learning approaches, incorporating the shift introduce minimal overhead and does not increase computational complexity."}, {"review_id": "Wbq4pSMNDc", "reviewer": "Reviewer_tYCN", "summary": "The authors present a theoretical work focused on challenges associated with building successor measures in goal-conditioned RL. In particular, the authors analyze a common assumption that the successor measure can be effectively modeled via low-rank representation and find that, whereas vanilla approaches are not guaranteed to admit a low-rank structure, such low-rank structure naturally emerges in shifted successor measures (where \"shift\" refers to skipping the first k time-steps of the trajectory before building the successor measure). Furthermore, the authors provide sample complexity bounds and errors for learning the shifted successor measure, which are shown to be related to the spectral recoverability of the successor matrix. Finally, the authors present a small experimental section consisting of a discrete, goal-conditioned maze. These experiments show that, in line with the provided theory, low-rank approximation works better with shifted successor measures.", "questions": "1.How restrictive are the assumptions made in corollary 1? In what types of setups do these hold?\n2.How do these theoretical considerations apply to continuous state/action environments?\n3.What is the significance of relaxed accuracy as compared to accuracy? Why do the policies with higher shifts perform relatively better in terms of relaxed accuracy than in terms of accuracy?\n4.Could the authors expand the intuition on why shifting would lead to a low-rank structure? Does this observation hold in more stochastic problems?", "limitations": "Authors could slightly improve the following aspects of their work:\n1.The limitations of the theoretical results - adding a paragraph summarizing the impact of the theoretical result on the practical workflows of reward-free RL, as well as the limitations associated with the assumptions \n2.The limitations of the experimental section - adding a paragraph discussing which assumptions and other elements of the theoretical analysis correspond to the experimental setup", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1.Despite being quite mathematically dense, the paper is clearly written (except for the experimental section).\n2.The manuscript provides an analysis of a common assumption used in reward-free RL with results that can inform future algorithm design.\n3.To the best of my knowledge, the strategy for obtaining the theoretical results is novel in the context of RL (although I did not check the correctness of the proofs).\n\nWeaknesses:\n1.The experimental section is relatively small and dense. It would be helpful to describe the experimental settings and the results in more detail. For example, a more direct discussion of the learning algorithm (e.g. hyperparameters), implications of the experiments with respect to the presented theory, and limitations of the experimental setup would be particularly helpful for the reader. Having said this, I understand that the theoretical analysis is the central contribution of this paper.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. Before answering your questions, we would like to briefly highlight our contributions.\n\nOur main contribution is to identify conditions under which low-rank structure naturally emerges in zero-shot reinforcement learning. Unlike prior work that assumes universal low-dimensional representations that generalize across tasks, e.g. Forward-Backward model (Touati and Ollivier, 2021; Touati et al., 2023) or goal-conditioned RL frameworks (Andrychowicz et al., 2017; Eysenbach et al., 2022b), we provide a theoretical basis for when and why such structure arises. \n\nSpecifically, we show that learning successor measures directly is statistically challenging, and demonstrate that a simple temporal shift of successor measures naturally induces low-dimensional representations. \n\nFurthermore, we present preliminary numerical results in section 6 and additional experiments in Appendix H that illustrate the benefits of learning shifted successor measures. We believe that our work lays the foundation for practical algorithms for policy learning via shifted successor measures.\n\n**On the scope and complexity of experimental validation.**\n        \nAs noted in the main text, Appendix H provides additional results on goal-conditioned tasks, which are discretized versions of standard (continuous) benchmarks for navigation tasks. There, we also discussed the impact of different data-collection policies and learning algorithms. Moreover, Appendix H.5 discusses extensions to non-tabular environments.\n        \nWe agree that evaluating on high-dimensional environments is a valuable future direction. However, the goal of our experiments is to validate the theoretical insights under controlled conditions, where factors can be isolated and analyzed rigorously. We believe the current experiments, together with our theoretical contributions, make the paper comprehensive and self-contained.\n\n**Restrictiveness of assumptions in Corollary 1.**\n        \nThe validity of the assumptions depend on the intrinsic dynamics but also on the choice of the policy. Overall, Corollary 1 requires the existence of an underlying structure (e.g. to have $\\sigma_1, \\ldots \\sigma_r$ of order $1$, and $\\sigma_{r+1}$ small), a sufficient shift (to have $\\xi(M_{\\pi,k})$ bounded), and a reasonably exploring policy (to have an underlying measure essentially invariant and uniform). We discuss these more in detail in Appendix C.1. The kind of setup where these apply well is for instance maze environments, like the four-room environment we give as an example in Theorem 4.\n\n**Extending the theory to continuous environments.**\n        \nThe notion of successor measure naturally extends to continuous state/action spaces using more general linear operators and measures instead of matrices (as is done in the forward-backward papers). We could extend Theorem 1 to this setting by discretization and leveraging smoothness properties of the dynamics (thereby requiring another assumption), in the spirit of the papers [1,2,3]. We restrict to the discrete setting first for simplicity, secondly because continuous settings are to be discretized anyway.\n\n[1] Devavrat Shah, Dogyoon Song, Zhi Xu, and Yuzhe Yang. Sample efficient reinforcement learning via low-rank matrix estimation. NeurIPS 2020.\n\n[2] Stefan Stojanovic, Yassir Jedra, and Alexandre Proutiere. Model-free low-rank reinforcement learning via leveraged entry-wise matrix estimation. NeurIPS 2024. \n\n[3] Jiaming Xu. Rates of convergence of spectral methods for graphon estimation, ICML 2018\n\n**On the significance of relaxed accuracy.**\n        \nIn many scenarios, reaching the exact goal is unnecessary - being close to the goal is sufficient. Relaxed accuracy captures this notion. As shown in Figure 4 in section 6, shifted successor measures not only improve exact goal-reaching with low-rank approximation (c), but also perform better at reaching the neighborhood of the goal (d). This demonstrates the robustness of shifted successor measures - even when they do not yield the optimal policy, they still outperform the non-shifted baseline in getting close to the goal.\n\nPolicies with higher shifts perform relatively better because they are better aligned with relaxed objectives: if we consider a $k$-shift and thus neglect to collect the reward in the first $k$ steps, this matters at most within a radius $k$ around the reward, where a sub-optimal trajectory may not be penalized. By looking at relaxed accuracy, we do not account for this sub-optimality.\n\n**Intuition behind why shifting induces low-rank structure.**\n        \nShifting corresponds to multiplying by $P_{\\pi}^k$, hence the shifted SM is the discounted sum of matrices $P_{\\pi}^{k+l}$ for $l\\ge 0$ which are in general more approximately low rank for large $k$: on the one hand, $I$ or $P_{\\pi}$ present in the non-shifted SM have no reason to be low-rank, while $P_{\\pi}^{k}$ converges to a rank $1$ matrix as $k \\rightarrow \\infty$ in the ergodic case (one eigenvalue is equal to $1$ and all others are strictly below $1$ in absolute value). The shift is a way to interpolate between these two extreme cases. This is the mixing intuition we make more rigorous in section 5.\n        \nFurthermore, this intuition works even better in more stochastic problems, since stochastic dynamics are more likely to be ergodic. Ergodicity may not be required however, provided we restrict to an appropriate sub-dynamics: see our discussion in Appendix C.1.\n\n**On the limitations of theoretical results.**\n        \nThanks for this remark. Regarding limitations, we discuss briefly the different terms of our upper bound after Theorem 1, while a more complete discussion is also given in Appendix C. We will highlight that more and summarize in the camera-ready version of the paper.\n\n**On the limitations of experimental results.**\n        \nWe thank the reviewer for this comment and refer them to Appendix H for a detailed description of the experimental setup. In the camera-ready version, we will add a paragraph in section 6 explicitly linking the experimental assumptions and design to the theoretical analysis."}, {"review_id": "k4FcVbdIr3", "reviewer": "Reviewer_6ieF", "summary": "Successor representation (SR) is a widely used approach for reward-free representation learning in reinforcement learning. This paper focuses on computing low-rank approximations of SR. However, if the underlying MDP is not low-rank, its successor representation is unlikely to be low-rank either, which introduces approximation error. To address this, the authors propose a new variant called the $k$-shifted SR, that captures the dynamics of policy $\\pi$ starting from time step  $k$.", "questions": "- If the MDP we aim to represent is not inherently low-rank, it’s unclear why we would prefer a low-rank representation in the first place. Why not simply use the standard full-rank successor representation (SR)? The justification for opting for a low-rank SR remains unclear. Is the goal to reduce memory usage, computational cost, or sample complexity? Or does it empirically lead to faster learning? These motivations need to be more explicitly articulated.\n- The paper shows results on the regret when estimating the shifted representation $M_{\\pi,k}$. However, it is unclear how this quantity is related to the regret of a policy that is computed via the shifted representation. How is $M_{\\pi,k}$ related to $M_{\\pi}$? One could accurately estimate  $M_{\\pi,k}$ but still get a bad policy. This could happen, for example, if the policy improvement method (e.g., GPI or policy iteration) amplifies the approximation error in an undesirable way. In my view, unless it is demonstrated that using  $M_{\\pi}$​ for policy computation leads to low regret in control, the importance of estimating it accurately remains unclear. This is likely my primary concern regarding the contribution. If this issue were resolved, the significance of the work would become much more apparent.", "limitations": "Some of the weakness listed below needs further comments on the text to address this potential limitations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is overall well written and easy to follow.\n- The proposed shifted SR is a natural and clever response to the limitations of low-rank SR in general MDPs.\n\nWeaknesses:\n- The relevance of the proposed approach is unclear. For instance, it remains uncertain whether obtaining the shifted-SR representation is actually useful for deriving good policies. The authors provide no theoretical guarantees about the quality of policies obtained after estimating the shifted-SR. Consequently, the practical utility of these representations is unclear.\nGiven this lack of clarity, the paper essentially proposes the problem of estimating shifted-SRs and a method to do so, but fails to establish why this is meaningful in the first place.", "was_revised": true, "final_justification": "Considering the initial criticism and the authors' responses to it, I have decided to raise the final grade and consider this paper to be suitable for acceptance.", "rebuttal": "Thank you for reviewing our paper. Before answering your questions, we would like to briefly highlight our contributions.\n\nOur main contribution is to identify conditions under which low-rank structure naturally emerges in zero-shot reinforcement learning. Unlike prior work that assumes universal low-dimensional representations that generalize across tasks, e.g. Forward-Backward model (Touati and Ollivier, 2021; Touati et al., 2023) or goal-conditioned RL frameworks (Andrychowicz et al., 2017; Eysenbach et al., 2022b), we provide a theoretical basis for when and why such structure arises. \n\nSpecifically, we show that learning successor measures directly is statistically challenging, and demonstrate that a simple temporal shift of successor measures naturally induces low-dimensional representations. \n\nFurthermore, we present preliminary numerical results in section 6 and additional experiments in Appendix H that illustrate the benefits of learning shifted successor measures. We believe that our work lays the foundation for practical algorithms for policy learning via shifted successor measures.\n\n\n**Motivation for using low-rank successor representations.**\n    \nThanks for this question: the objective of our paper is really to answer it! Without any structure, learning cannot be statistically efficient. That is why (and we explain this in the intro) many successful existing approaches in RL assume the existence of a low-rank structure, usually by assuming low-dimensional representation vectors $\\phi(s,a)$ and $\\psi(g)$. In this paper, we explain how such a structure appears naturally and universally (section 5), and we exemplify how the statistical efficiency of RL estimation procedure is improved by leveraging this structure (section 4). Note however that our results in Theorem 1 are always valid (not only for low-rank) and yet show the impact of having low-rank structures.  \n\n**Connection between shifted-SR and optimal policy.**\n\nWe thank the reviewer for raising this important question. There are three crucial points in addressing this issue:\n\n(a) **On the infeasibility of estimating $M_\\pi$.** If the reward function is known, the matrix product $M_{\\pi} R$ directly gives the Q-function. Therefore, estimating $M_{\\pi}$ allows policy evaluation for all rewards, which is of prime interest for transfer learning, multi-goal RL, etc. However, as discussed earlier, we argue that accurately estimating $M_{\\pi}$ is generally infeasible due to the absence of a low-rank structure, and propose shifted successor measures as a way to circumvent this issue. For a moderate shift, $M_{\\pi,k}$ remains reasonably close to $M_{\\pi}$, while being more easily recoverable using low-rank approximation.\n\n(b) **Shifted-SR recover (nearly)-optimal policy in Goal Conditioned RL.** In sparse reward settings, the most challenging in practice, policy updates based on shifted objectives yield policies that coincide with the optimal policies except when very close to the goal. Intuitively, for a fixed shift parameter $k$, if the goal is more than $k$ steps away from the current state, the Q-values computed using $M_{\\pi,k}R$ are identical to those computed from $M_{\\pi}R$. This ensures that the resulting policy is optimal until the agent enters the $k$-neighborhood of the goal, where exact optimality cannot be guaranteed. Nonetheless, as shown empirically in section 6 (and Appendix H), shifted-SR still recovers nearly optimal policies in practice.  \n\n(c) **On the importance of entrywise guarantees for good policy recovery.** Our work focuses on policy evaluation, and in this context, the entrywise guarantees we provide i.e. bounds $\\Vert M - \\widehat{M}\\Vert_{2\\to\\infty}$ are crucial. Such guarantees imply that greedy policy $\\pi_{\\widehat{M}}$ derived from $\\widehat{M}$ will perform well. This contrasts with weaker guarantees in global norms such as the Frobenius norm, which do not provide the same level of assurance for individual states. Thus, the strong entrywise bounds we establish are central to ensuring that accurate estimation of $M$ leads to high-quality policies."}]

Author rebuttal:

Meta-review: A lot of RL problems become easier if we can estimate the successor measure for a given environment and behavior policy: a matrix whose (s, a, s’, a’) element is the expected discounted frequency of visits to (s’, a’) if we start at (s, a). Many approaches to estimating this matrix implicitly assume that it is low rank. This paper points out (1) that it requires restrictive assumptions to ensure low rank, (2) that a related matrix, the shifted successor measure, can be low rank under different (possibly weaker) assumptions, and (3) that the shifted successor measure can be almost equally useful for many RL problems. The k-shifted successor measure has elements equal to the expected discounted frequency of visits to (s’, a’) if we start at (s, a) *and ignore the first k time steps*.

The bulk of the paper provides definitions and analysis to prove low rank and reconstruction guarantees: when is the shifted successor measure matrix approximately low rank, and when does this lead to accurate recovery from few samples. Some of the quantities that the bounds depend on:
* the ratio between the visitation distribution of the behavior policy and the weights used to do the SVD
* the distance from uniformity of this visitation distribution (this seems somewhat restrictive, and isn’t discussed much in the main paper)
* the existence of an appropriate rank r: the r-th singular value should be large enough and there should be enough of a gap to the (r+1)-st singular value
* the incoherence (at rank r) of the successor measure matrix — if it is too coherent, we have to get lucky enough to visit a few important states if we want to collect enough data to have low error.

The paper provides a bit of intuition about sufficient conditions for the rank/gap condition to hold. One condition is based on a new variant of Poincaré inequalities; it yields sharp results but requires information that may not be available in practice. Another condition is based on local mixing: e.g., when the states are divided into a few rooms, and the process mixes rapidly within a room and slowly between rooms.

The paper doesn’t spend much time on the question of when good recovery of the successor measure is enough to ensure that RL succeeds. It references prior (classic) results that relate performance of greedy policy improvement to recovery error in (\infty, \infty) norm, as well as prior positive experimental results that do RL from successor measure estimates based on low-rank features. Further information came up in the reviewer-author discussion, and would be helpful to add to the paper. It also seems like RL complexity measures like Bellman rank may be useful in connecting recovery to performance (or if they are not, it would be helpful to have an explanation of why).

Finally, the paper gives numerical experiments: it estimates the successor measure from exploration data in some benchmark environments, then uses it to do greedy policy improvement. In keeping with the theory, all environments are tabular. And in keeping with the theory, nonzero shifts do outperform the previous standard approach of no shift. The experiments also illustrate that moderate values of the shift are the ones that perform best. As pointed out in the discussion, this is helpful since in practice we won’t know enough to estimate the optimal shift, so we need a good range for hyperparameter search. Also pointed out in the discussion is that the experiments section is dense, and a fuller description of the methods would be helpful.

I noticed while compiling this meta-review that there don’t seem to be citations to the literature on predictive state representations / observable operator models; these would be helpful to add, since that line of work is exactly about RL using the assumption of low-rank transitions.

Overall the paper does a good job of setting up an interesting set of questions and goes a long way toward answering them. As an initial attempt, some assumptions are strong (e.g., restriction to tabular case, requirement of full exploration, goal of recovery in a very strong norm), but this is appropriate: the paper is the first to aim at a novel spot in between pure theory and relevance to practice, and mostly hits this spot. The writing is clear (though dense in places), the math brings in appropriate techniques, the bounds seem reasonable, and the paper tries to explain where each term in the bounds comes from.
Decision: Accept (spotlight)