The surprising efficiency of temporal difference learning for rare event prediction

Authors: xiaoou  cheng
jonathan  weare
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:56:31

Abstract: We quantify the efficiency of temporal difference (TD) learning over the direct, or Monte Carlo (MC), estimator for policy evaluation in reinforcement learning, with an emphasis on estimation of quantities related to rare events. Policy evaluation is complicated in the rare event setting by the long timescale of the event and by the need for \emph{relative accuracy} in estimates of very small values.  Specifically, we focus on least-squares TD (LSTD) prediction for finite state Markov chains, and show that LSTD can achieve relative accuracy far more efficiently than MC.  We prove a central limit theorem for the LSTD estimator and upper bound the 
  \emph{relative asymptotic variance}
  by simple quantities characterizing the connectivity of states relative to the transition probabilities between them. Using this bound, we show that, even when both the timescale of the rare event and the relative accuracy of the MC estimator are exponentially large in the number of states, LSTD maintains a fixed level of relative accuracy with  a total number of observed transitions of the Markov chain that is only \emph{polynomially} large in the number of states.

Main paper: 
 introduction: 
 Prediction of the future behavior of a dynamical system from time series observations is a fundamental task in science and engineering. One need only remember the weather forecast consulted this morning to appreciate the substantial intersection this problem has with our everyday lives. Beyond its own obvious importance, prediction is also a key component in modern machine learning tasks like reinforcement learning, where the rules governing the dynamical system are adjusted to optimize some reward. Exciting applications in that field, like self-driving cars, have captured public imagination.Prediction is made particularly difficult when the future behavior of interest involves some rare or extreme event. Examples include extreme weather or climate events, failure of reliable engineering products, and the conformational rearrangements that determine critical functions of biomolecules in our bodies. Precisely because of their out-sized impact on our lives and society, rare and extreme events are the most important to predict. Unfortunately, by definition, data sets often contain relatively few examples of these events. In this article we ask: can rare events be predicted accurately with time series data sets much shorter than the typical timescale of the event? The surprising answer is Yes. Our mathematical results support recent studies demonstrating accurate rare event prediction with limited data using methods related to those studied here, including in state-of-the-art application settings and for very rare events [Thiede et al., 2019 , Strahan et al., 2021 , Finkel et al., 2021 , 2023b , Antoszewski et al., 2021 , Lucente et al., 2021 , Finkel et al., 2023a , Strahan et al., 2023a , Jacques-Dumas et al., 2023 , Strahan et al., 2023b , Guo et al., 2024] .Within the context of reinforcement learning, "prediction" refers to policy evaluation, that is, calculation of the value function of states given a policy [Sutton and Barto, 2018] . Prediction is the foundation for policy improvement in control problems. In this work, we focus on prediction for Markov chains on a finite state space. While many dynamical systems of physical interest evolve in continuous spaces, this so-called "tabular" setting is the most common for mathematical analysis. Moreover, some practical algorithms for prediction problems in continuous space begin with a projection onto a finite state Markov process [Thiede et al., 2019 , Finkel et al., 2021 , 2023a , Jacques-Dumas et al., 2023] . For those algorithms our analysis can be viewed as addressing estimation (but not approximation) error .Specifically, we formulate a prediction problem in terms of a Markov reward process (MRP) ([n] , P, R), where [n] = {1, 2, . . . , n} is the state space, P is the Markov transition kernel with P (i, j) = P [X t+1 = j | X t = i], and R is a deterministic, non-negative reward function. Time dependence and randomness of R can be included by an enlargement of the state space. Our goal is to estimate a value function of the general form1 EQUATIONwhere D is a subset of [n], T = min{t ≥ 0 : X t / ∈ D} is the escape time from D, and the subscript i on the expectation indicates that X 0 = i. By appropriate choice of R, we can consider both cases in which the escape time from D is very large and cases in which only low probability escape paths accumulate significant reward. These are the typical situations for rare event statistics, where the reward R and the set D are specified by the application. In the example of self-driving cars, when investigating the rare event that the car crashes, D is the set of all states in which the car has not crashed.The prediction problem has been extensively analyzed in the reinforcement learning literature [Sutton and Barto, 2018, Dann et al., 2014] . Our problem's main point of departure from that literature is the central role of the escape event from D in (1). We are specifically interested in cases in which E j [T ] can be very large so that the length of a single escape trajectory can be very large, and/or cases in which large values of the reward functions are very unlikely so that u can be very small.Our task is to learn an estimate of u from a set of M samples {X ℓ 0 , X ℓ 1 , . . . , X ℓ τ ∧T ℓ } M ℓ=1 of X 0 , X 1 , . . . , X τ ∧T with {X ℓ 0 } M ℓ=1 drawn from some (possibly unknown) initial probability distribution µ which is supported in D. Here and below we use the shorthand a ∧ b = min{a, b}. The deterministic positive integer τ , which we will refer to as a lag time, limits the length of the trajectories in the data set. In practical applications, the sample trajectories are often correlated, for example because multiple length τ trajectories can be harvested from a single longer trajectory. Here, to simplify the analysis, we assume that the trajectories are drawn independently.The most direct estimator of u(i) is the Monte Carlo (MC) estimatorû(i) = 1 M i Mi ℓ=1 T ℓ t=0 R X ℓ t , when M i > 0,where M i is the number of samples with X ℓ 0 = i, i.e. M i = M ℓ=1 1 {i} (X ℓ 0 ). The estimator is undefined for i ∈ D with M i = 0. The MC estimator does not allow finite values of τ (unless T is bounded by a constant). When the escape event is rare, T is very large and the MC estimator requires data sets containing very many observed time steps of X t . Moreover, estimators of rare event statistics are evaluated based on the amount of data required to achieve a desired relative error [Bucklew, 2004] . In the rare event setting, u(i) can be extremely small because of the low probability of the event to happen. In this case, assuming µ(i) > 0, control of the relative variance, Var [û(i)] /u 2 (i), often requires M ∝ 1/u(i) trajectory samples for the MC estimator. This scaling is fatal when u(i) is very small. Temporal difference (TD) schemes, on the other hand, express u as the solution to a certain Bellman equation [Sutton, 1988] . They enforce temporal local consistency of the estimate of the value function.As such, TD methods can accommodate any positive choice of τ , while MC methods require that each trajectory be observed until escape from D (i.e. τ = ∞). TD schemes are used heavily in reinforcement learning and they are often observed to out-perform MC [Sutton and Barto, 2018] . However, a quantitative understanding of the advantages of TD compared to MC remains elusive. In practice, there are several variants of TD schemes: parametric or tabular, online or batch. In this work, we stick to the simplest setting: the least-squares TD (LSTD) estimator [Bradtke and Barto, 1996] in the tabular setting of a finite state MRP. Our goal is to clearly characterize the benefit of the LSTD estimator over MC for predictions related to rare events in this setting.TD schemes begin with the observation that, for any choice of τ , u in (1) solves the linear systemEQUATIONwhereS(i, j) = P (i, j) for i ∈ D and S(i, j) = δ ij for i / ∈ D,is the transition operator of X t∧T , S τ is the τ th power of S and RD (i) = R(i) for i ∈ D while R D (i) = 0 for i / ∈ D.In the limit τ → ∞, (2) becomes (1). In our theory and examples, we will see that the choice of τ can have a dramatic effect on the performance of the estimator.TD methods use trajectory data to find an approximate solution to (2). Specifically, the LSTD estimator ũ in this tabular setting is the solution to a linear system where the transition matrix S in ( 2) is approximated with trajectory data. We set S0 = I and, for t = 1, 2, . . . , τ ,St (i, j) = 1 M i M ℓ=1 1 {(i,j)} X ℓ 0 , X ℓ t∧T ℓ for M i > 0 and St (i, j) = δ ij for M i = 0.Unlike S t , St are not powers of a single matrix. When it exists, the τ -step LSTD estimator, ũ solvesEQUATION(Like the MC estimator, ũ(i) is undefined when M i = 0). In the τ → ∞ limit, the τ -step LSTD and MC estimators are equivalent. We therefore occasionally refer to the Monte Carlo estimator as the τ = ∞ estimator.We pause now to consider what classical perturbation theory for linear systems has to say about the feasibility of estimating u, the solution of (2), by ũ, the solution to (3). Clearly (3) only requires access to trajectories of length τ , but how sensitive is the solution of (2) to perturbations in S? If it is very sensitive then any reduction in data requirements from shorter trajectories may be offset by a need for many more trajectories. Classical perturbation theory tells us that errors S t -St can, in the worst case, be amplified in u -ũ by a factor of the condition number κ τ = ∥(I -S τ D ) -1 ∥∥I -S τ D ∥, where S τ D is the matrix obtained from S τ by setting to zero any row or column with index in D c [Demmel, 1997] . As the next lemma shows, when typical values of T are much larger than τ , ∥(I -S τ D ) -1 ∥ will be very large. The proof of Lemma 1 is in Appendix A. Lemma 1. For any consistent matrix norm, if the restriction of S D to row and column indices in D is irreducible and aperiodic, then∥(I -S τ D ) -1 ∥ ≥ E ν [T ]/τ where ν(i) = lim t→∞ P [X t = i | T > t]is the quasi-stationary distribution and the subscript on the expectation indicates that X 0 is drawn from ν. (See Collett et al. [2012] for more about the quasi-stationary distribution).While it is possible that a small value of ∥I -S τ D ∥ can compensate for a large value of E ν [T ]/τ and result in a moderate condition number, for many rare event problems this is not the case. For example, for the system studied in our numerical experiments in Section 3, ∥I -S D ∥ is bounded away from zero even as the escape event becomes increasingly rare (see Appendix B).Thus it would seem that we are forced to choose between two doomed options: choose τ small to control the length of trajectories we need to observe but observe a huge number (M ∝ E ν [T ]/τ ) of them to drive down the error in St , or observe very long trajectories (τ ∝ E ν [T ]) to control κ τ . With either of these choices we would not expect TD to significantly outperform MC.A primary goal of this article is to explain that, in many (perhaps most) cases, this is a false choice. The worst case analysis that characterizes the classical perturbation theory is, by design, pessimistic. But as we will explain, in our setting it is wildly pessimistic. With a few simple and practically relevant assumptions we will be able to show that τ -step LSTD can achieve remarkably accurate estimates with remarkably little data.Throughout this paper we quantify the relative accuracy of ũ(i) by the relative asymptotic variance σ 2 i /u 2 (i) where σ 2 i is the variance of the limiting normal distribution in a central limit theorem for ũ(i) established in Theorem 1. Also in Theorem 1, we provide an upper bound on the relative asymptotic variance by simple quantities characterizing the connectivity of states relative to the transition probabilities between them. Crucially, neither the condition number κ τ , nor any expectation of T , appear explicitly in the bound. Next, we turn our focus to the rare event setting, which we characterize via the large n behavior of the estimator. In this setting both the typical escape time and the relative variance of the MC estimator can scale exponentially with n. As we show in Theorem 2, however, the relative asymptotic variance of the LSTD estimator scales, at worst like n 3 .Since it first appeared in [Sutton, 1988] , there have been numerous variants of TD [Bradtke and Barto, 1996 , Dann et al., 2014 , Lillicrap et al., 2019] . Early theoretical analysis of TD focused on asymptotic convergence with linear value function approximation [Jaakkola et al., 1993 , Dayan and Sejnowski, 1994 , Tsitsiklis and Van Roy, 1997] , along with examples of divergence [Baird, 1995, Tsitsiklis and Van Roy, 1997 ]. More recently, nonasymptotic convergence analysis of TD has been performed [Bhandari et al., 2018 , Dalal et al., 2018 , Srikant and Ying, 2019 , Cai et al., 2019] .Besides its own convergence, a long-considered question for TD is when and how it outperforms MC. While practical experience suggests that TD is more efficient than MC, a comprehensive theory is lacking. Grunewalder et al. [2007] and Grünewälder and Obermayer [2009] proved that LSTD is at least as statistically efficient as MC, but the improvement is not quantified. Cheikhi and Russo [2023] expresses the relative benefit of TD over MC by the inverse trajectory pooling coefficient, which facilitates interpretation of the ratio of asymptotic variances. But how that translates to quantitative improvements requires further elucidation. As far as we are aware, prediction for rare event problems has not been analyzed in the reinforcement learning literature.TD enforces temporal consistency for trajectory data. Trajectory data has been utilized in applications more broadly. Markov state models [Husic and Pande, 2018] and dynamic mode decomposition methods [Schmid, 2022] were developed in the molecular dynamics and fluid dynamics communities respectively and have been successful at estimating eigenvectors and eigenvalues of Markov transition (or Koopman) operators from trajectory data in state-of-the-art applications. The dynamical Galerkin approximation [Thiede et al., 2019] method extends those approaches to the prediction problem studied here and has been used to study rare events in molecular dynamics and climate science [Strahan et al., 2021 , Antoszewski et al., 2021 , Finkel et al., 2021 , 2023a , Guo et al., 2024] . Despite widespread application in the study of various rare events over several decades, the present article is the first theoretical evidence that trajectory analysis methods can be effective tools specifically for rare events.X D -→ N (µ 0 , σ 2 0 )indicates that a random variable X converges in distribution to a normal distribution with mean µ 0 and variance σ 2 0 . For any subset A ⊆ [n], we define the hitting time T A = min{t > 0 : X t ∈ A}. When X t never hits A, T A = +∞. When the set A contains only one state i, we use T i for simplicity. Note that in (1), T counts from t = 0 instead. While S is the transition probability matrix for the Markov chain X t∧T , we define another Markov chain Y τ t whose transition probability matrix is S τ . For Y τ t , we define its hitting time to be T τ A = min{t > 0 : Y τ t ∈ A}. We define T τ = min{t ≥ 0 : Y τ t ∈ D} as a counterpart of T for X t . We use e i for the ith standard basis vector, i.e. e i (j) = δ ij . For any two quantities a and b, a ≳ b means that there exists a positive constant C independent of n such that a ≥ Cb. Similarly, a ≲ b means that a ≤ Cb. 
an upper bound for relative asymptotic variance: 
 As previous authors have done [Cheikhi and Russo, 2023] , we will characterize the error of the LSTD estimator using a central limit theorem. Unlike previous work, we will also provide a simple upper bound on the relative asymptotic variance that clearly distinguishes the LSTD estimator from the MC estimator. Our subsequent analysis of the LSTD estimator in the rare event setting will be derived from this bound. Theorem 1. Suppose µ(i) > 0 for all i ∈ D and P is irreducible. Then, as the number of samplesEQUATIONwithσ 2 i = k∈D 1 µ(k) e T i (I -S τ D ) -1 e k 2 E k τ -1 t=0 R D (X t∧T ) + u(X τ ∧T ) -u(k) 2 .(5)Moreover, the relative asymptotic variance σ 2 i /u 2 (i) satisfies the upper boundσ 2 i u 2 (i) ≤ k∈D, ℓ∈[n], ℓ̸ =k τ t=1 S t (k, ℓ) µ(k) Q τ (k, ℓ) 2 (6)where we have introduced the key quantityQ τ (k, ℓ) = P k T τ ℓ < T τ k ∧ T τ D c \{ℓ} .An important special case that will include one of the examples studied in Section 3, occurs when the reward function R is zero in D (but non-zero in D c ). In this case we can strengthen the bound in Theorem 1 by only including S τ in the numerator. Corollary 1. Under the same assumptions as in Theorem 1 but with R(i) = 0 for any i ∈ D,EQUATION)Let us take a moment to parse the bounds in Theorem 1 and Corollary 1. The bounds tell us that if the sum is bounded, our estimator achieves entry-wise relative accuracy, indicating that even when u(i) is extremely small, the error in ũ(i) can be much smaller (depending only on M ). But the denominator is the real star of the show. It is the sum of the probabilities of all paths connecting state k and state ℓ that do not return to k and do not exit D (except possibly through ℓ). In particular Q τ (k, ℓ) ≥ S τ (k, ℓ). While the probability Q τ (k, ℓ) can be very small for most pairs (k, ℓ), evidently it is the size of Q τ (k, ℓ) 2 relative to S t (k, ℓ) for t ≤ τ (or only S τ (k, ℓ)) that matters. Fortunately, in many cases, we can expect Q τ (k, ℓ) 2 to be much larger than S τ (k, ℓ) for a good choice of τ . We will quantify this statement in the rare event setting in Section 4.A quantity very similar to Q τ (k, ℓ) appears in the matrix analysis literature [Thiede et al., 2015] as a measure of the sensitivity of the relative accuracy of the invariant distribution of a Markov chain to entry-wise perturbations in its transition probability matrix. The proofs of Theorem 1 and Corollary 1 are given in Appendix C. Lemma 2 in Appendix C, which is used to bound the variation in u between states, is key to the argument. 
experiments: 
 We now consider two example problems that illustrate the challenges posed by rare event prediction.For both problems the statistical efficiency of the MC estimator degrades exponentially in the state space size n. Our goal is to see whether or not LSTD's performance degrades similarly as n increases, and, in so doing, to motivate our final bounds on the relative asymptotic variance of LSTD established later in Section 4. The examples and numerical results presented in this section are exactly consistent with the assumptions and results presented in Section 4.Both problems are based on a one dimensional nearest neighbor chain X t ∈ [n] with transition rulesEQUATIONwith P (1, 0) = P (n, n + 1) = 0 on the boundary. Here p is the invariant probability vector of P ,EQUATIONwhich has modes around i = 1, i = (n + 1)/2, and i = n, that become more sharply peaked as n increases. The escape time from any of these modes scales exponentially with n. We will be interested in predictions related to the escape of X t from D = [n] \ {1, n}, and choose µ to be the uniform distribution on D.Before moving on to the specific problem statements, we point out that despite the exponentially long waiting time to transition between the modes of p, transitions between nearest neighbor states remain stable as n increases. In fact, for i ∈ D, P (i, i ± 1) ≥ 1 2(1+e) . Stable local transition probabilities such as these play a key role in our upper bounds in Section 4, where they are used to lower bound Q(k, ℓ) in ( 6).The mean first passage time. The mean first passage timeu(i) = E i [T ] solves (2) with R(i) = 1 for i ∈ D and R(i) = 0 for i / ∈ D.We plot the mean first passage time for n = 20, 40, and 80 in the left panel of Fig. 1 . Evidently the largest values of E i [T ] scale exponentially with n. In Appendix B, we prove that, near i = (n + 1)/2,EQUATION)Therefore the trajectories required by the MC estimator will include a number of transitions of X t that scales exponentially with n. We compare the performance of the MC estimator of the mean first passage time to that of the LSTD estimator, ũ, found by solving (3) with τ = 1. In the middle panel of Fig. 1 we plot the relative asymptotic variance, σ 2 i /u 2 (i), for the same values of n. In the same panel we plot empirical estimates of the the (non-asymptotic) relative mean squared error (MSE), M MSE [ũ(i)] /u 2 (i), with M = 10n 3 . The empirical relative MSE estimates are computed by generating 30000 independent copies of the LSTD estimator. Remarkably, the relative MSE of the LSTD estimator grows more slowly than n 3 . Meanwhile, near the boundary of D, the relative MSE of the MC estimator (computed exactly) grows exponentially fast with n, as can be seen in the right panel of Fig. 1 . The committor. We now consider estimation of the committor functionu(i) = P i [T n < T 1 ] for i ∈ [n] \ {1, n} and u(i) = 1 {n} (i) for i ∈ {1, n}.The committor corresponds to the choice R(i) = 0 for i ̸ = n and R(n) = 1. Because E i [T ] can be exponentially large, the MC estimator of the committor again requires a data set containing exponentially long trajectories of X t . Moreover, in Appendix B, we prove that u(i) can be exponentially small in n, asEQUATIONas is evident in the plot of the committor for n = 20, 40, and 80, in the left panel of Fig. 2 . As a consequence, the relative MSE of the MC estimator, plotted in the right panel of Fig. 2 , grows exponentially fast with n. As can be seen from the middle panel of Fig. 2 , however, the relative asymptotic variance of the LSTD committor estimator with τ = 1 grows more slowly than n 3 . Again empirical estimates of the relative MSE of the LSTD estimator with M = 10n 3 agree well with corresponding relative asymptotic variances and show the same trend. Together, the mean first passage time and the committor estimation problems in this section strongly suggest a significant (polynomial versus exponential in n) advantage for TD methods over MC. In the next section we will prove that the performance advantage observed on these two examples holds in significant generality.Effect of the lag time. In the above experiments we have examined the error of the LSTD estimator with τ = 1. In practice, the best choice of τ is long enough to avoid a nearly diagonal S τ , but not so long as to lose the efficiency advantage of TD over MC that we have just observed. Our bounds in Theorem 1 also change with τ . To better illustrate the effect of τ on the relative asymptotic variance of the LSTD estimator and on our bounds, we now consider a "lazier" version of the Markov chain in (8). Specifically, we defineP (i, i ± 1) = p(i±1)10(p(i)+p(i±1)) for i ± 1 ∈ D, with the same boundary conditions as before. We again consider estimates of the mean first passage time and the committor, now with fixed n = 40. We plot the maximum of the relative asymptotic variance, σ 2 i /u 2 (i), over i ∈ D in Fig. 3 , along with the bound (6) for the mean first passage time in the left panel and (7) for the committor in the right panel. Though the plots do not extend to values of τ comparable with the largest values of E i [T ], the relative variance of the MC estimator corresponds to the asymptote of the true relative variance toward the right hand side of each plot. We observe that the true relative variance of the LSTD estimator is minimized in both cases for a choice of τ ≈ 30 and that, for this choice, the relative variance of the LSTD estimator is significantly smaller than the relative variance of the MC estimator. The bounds in ( 6) and ( 7) are designed to capture the high accuracy of LSTD for relatively small values of τ and we indeed see that they deteriorate as τ becomes very large. However, at least in the committor case, the bound accurately reproduces the initial decrease in error that occurs when τ is increased above τ = 1.Effect of the initial distribution. So far, in our experiments, we have chosen µ to be the uniform distribution on D. A natural alternative strategy is to harvest many short trajectories from Figure 3 : The bound and the truth for the maximum relative asymptotic variance of the mean first passage time and the committor with varying lag time τ . The number of states fixed at n = 40. The relative asymptotic variance bounds for the mean first passage time and the committor are from ( 6) and ( 7) respectively. a single, much longer trajectory. Under ergodicity assumptions on P , these short trajectories are then approximately drawn from the invariant distribution of P . In Fig. 4 , we present the relative asymptotic variance and the empirical estimates of the relative MSE of the mean first passage time and the committor, with P being the same as in ( 8), and µ chosen to be the invariant distribution p in (9) conditioned within D. For τ = 1 and n = 20, 40, and 80, remarkably, the maximum relative asymptotic variances of the LSTD estimators grow exponentially with n. With M = 10n 3 , the empirical relative MSE estimators with 30000 independent copies of the LSTD estimators agree well with the relative asymptotic variance for n = 20 and 40. For n = 80, the empirical linear system (3) fails to define the LSTD estimators with high probability, and the empirical error is undefined. These results should be contrasted with the much smaller errors shown in the middle panels of Figs. 1 and 2, corresponding to uniformly chosen initial conditions. The results indicate that the choice of µ can also have a significant impact on the performance of LSTD for prediction of rare events. 
rare event assumptions and upper bound: 
 Our final relative asymptotic variance bounds will rigorously establish the dramatic advantage of TD over MC that we observed in the experimental results of Section 3. As in that section, we focus on the behavior of relative variance as n increases. Our results rely on several basic assumptions. On the one hand, all of these assumptions are satisfied by the Markov chain examined in Section 3. On the other hand, the results in this section cover considerably more general Markov chains. The assumptions concern certain structural properties of the Markov chain as n increases, but crucially, they allow both the typical escape time and the relative variance of the MC estimator to grow exponentially in n.To ensure that a unique ũ will exist for large enough M , we make the following minorization assumption on µ.Assumption 1 (Lower bound on µ). For some constant α > 0, independent of n, and all i ∈ D, µ(i) ≥ α n .Recall that the uniform distribution on D was used to generate initial conditions for the numerical tests described in Section 3. The invariant distribution p in (9) conditioned within D, instead, violates this assumption, as its minimum is exponentially small in n.As mentioned in Section 1.2 the perturbations, Sτ -S τ , relevant for analysis of the LSTD estimator are far from the worst case perturbations characterizing classical perturbation bounds for Eq. ( 2). Each entry of the matrix St is the empirical frequency of a specific transition. As a result, the variance of St (i, j) is proportional to S t (i, j) (1 -S t (i, j)) ≤ S t (i, j), and we can characterize the perturbations by characterizing the entries themselves. Different entries of S t can have very different magnitudes, and many Markov processes exhibit higher transition probabilities between states that are "close" according to some metric and small transition probabilities between states that are "far away". To express this notion in assumptions without resorting to any topology within which the state space may be embedded, we upgrade [n] to an unweighted directed graph G by including edges only along transitions with significant probability. Our additional assumptions will be stated in terms of properties of this "minorizing graph."Figure 5 : Left: an undirected graph with edges colored according to the transition probabilities. An edge with darker color corresponds to a transition with higher probability. Right: after pruning edges with low transition probabilities, the minorizing graph stays connected. Specifically, we introduce a directed edge from state i ∈ G to another state j ∈ G if S τ (i, j) ≥ c, where c is a positive constant independent of the number of states n.Assumption 2 (Connected minorizing graph). For some constant c > 0, independent of n, the minorizing graph G is connected.When P is irreducible, as assumed in Theorem 1, and n is fixed, we can always find a c > 0 so that G is connected. Assumption 2 emphasizes the independence of n, asserting that the transition probabilities above the threshold c can, on their own, preserve the connectivity of the graph while n increases. Recall that the Markov chain studied in Section 3 satifiesP (i, i ± 1) ≥ 1/(2(1 + e)),implying that Assumption 2 is satisfied with the choice c = 1/(2(1 + e)).Let d(i, j) be the length of the shortest path from state i to state j in G. When the graph is undirected, d is a distance on G, but it need not be. Finally, we characterize the decay of the transition probabilities of pairs of states that are "far away" according to G. Assumption 3 ("Sub-Gaussian" transition probability tails). For some constants β > 0 and C, independent of n, for all i ̸ = j, and t ≤ τ , S t (i, j) ≤ Ce -βd 2 (i,j) .Assumption 3 stipulates that transition probabilities decay fast enough for distant states in G. For the Markov chain studied in Section 3, when τ = 1 this assumption is satisfied because transition probabilities are zero for states that are not nearest neighbors. Assumptions 2 and 3 essentially characterize the locality of the transitions. These assumptions are practically reasonable even when, as in the example in Section 3, the global landscape of the transitions exhibits challenging traits such as multi-modality.Illustration. The left panel of Fig. 5 , depicts a general (symmetric) Markov chain on a graph. Darker edges indicate higher transition probabilities. The transition probabilities are chosen to decay with Euclidean distance in the plane, consistent with, for example, a Gaussian transition kernel in the plane. The minorizing graph on the right retains only those edges exceeding the threshold c, which is chosen large enough to remove most distant edges, but small enough to result in a connected graph.In Section 3, we considered the effect of the choice of τ on relative asymptotic variance. In that example, a larger choice of τ initially increased the probability of nearest neighbor transitions and would allow for a larger choice of c. As τ increases further however, the probabilities of distant transitions would become larger, potentially decreasing the maximum allowed choice of c and possibly requiring a smaller choice of β and/or a larger choice of C in Assumption 3. The quantitative interplay among c, β and C are determined by the specific Markov chain under study, but we expect similar behavior for common transition probabilities such as Gaussian transition kernels.As the experiments in Section 3 clearly demonstrate, these assumptions allow both the typical escape time and the relative variance of the MC estimator to scale exponentially with n. The failure of MC in these scenarios does not contradict this paper's theoretical results because the MC estimator does not satisfy Assumption 2. Indeed, the MC estimator corresponds to τ = ∞, for which S τ (i, j) can only be non-zero if i ∈ D, j ∈ D c .With these assumptions, we can now state our upper bound for the rare event setting, whose proof is very simple but informative. The key idea is that, under these assumptions, Q τ (k, ℓ) in the denominator is indeed much larger than the transition probabilities S t (k, ℓ) in the numerator. Theorem 2. Under Assumptions 1, 2 and 3, we have the following asymptotic variance bound:EQUATION)When R(i) = 0 for all i ∈ D,EQUATION)Proof of Theorem 2. Because Q τ (k, ℓ) is the sum of the probabilities of all paths connecting states k and state ℓ that do not return to k and do not exit D (except through ℓ), Assumption 2 implies that k,ℓ) .Q τ (k, ℓ) ≥ c d(Plugging this bound and the ones in Assumptions 1 and 3 into (6) we find thatσ 2 i u 2 (i) ≤ C α τ n k∈D, ℓ∈[n], ℓ̸ =k e -d(k,ℓ)(2 log c+β d(k,ℓ)) .Optimizing the summand over d(k, ℓ) gives the bound in ( 12). The bound in (13) follows from the same argument using (7) instead of (6).Remarkably, the total amount of data (measured in observed transitions of X t ) required to achieve a fixed relative accuracy has reduced from as bad as exponential in n for the MC estimator to no worse than n 3 for the short trajectory estimator. 
conclusions and future work: 
 In this article we show that the LSTD method can produce relatively accurate estimators of rare event statistics with a data set of observed Markov chain transitions that is dramatically smaller than would be required by the Monte Carlo estimator. In particular, the LSTD estimator can achieve relative accuracy with a number of observed transitions much smaller than typical timescale of the rare event.This contrasts with the classical worst case perturbation bounds, which predict a large error when the typical timescale of the rare event is large.Generalization of our basic conclusions beyond the tabular setting is a natural goal for future work.Our proof strategy can be used to establish general, entry-wise perturbation bounds for linear systems of the form in (2). A version of those bounds that applies to Markov processes in continuous spaces would have many interesting consequences, including in the analysis of both approximation and estimation error for TD approaches beyond the tabular setting.We have not considered online TD approaches [Sutton and Barto, 2018 ]. In the tabular setting considered here, standard online TD corresponds to a variant of classical Richardson iteration in which the residual of ( 2) is replaced by an independent realization of the residual of (3) at each iteration. Both deterministic Richardson iteration and online TD will converge very slowly when the typical timescale of the rare event is large. This issue has been explored in Strahan et al. [2023b] , where the authors suggest a batch version of subspace iteration for online policy evaluation and demonstrate improved convergence. The data requirements of that scheme should be studied theoretically.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [No] Justification: The paper contains experiments, but the main part of codes is just solving some linear systems. We provide all details of experiment settings, and readers should be able to write their own code and reproduce our results. There is no dataset used by this paper.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: For experiments in Section 3, the corresponding settings are stated there.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. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: Our theoretical result is asymptotic in nature, so such error bars are not directly related to the goal of this paper. In section 3, along with the theoretical relative asymptotic variance, we also provide plots of relative empirical variance with large sample sizes. This shows an agreement between the reality and the theory, but not to an extent of an actual error bar.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, confidence 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, or 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. • It 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 a 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 of range (e.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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: There are experiments involved in the paper in Section 3, but they are quite light in computational resources. The goal of experiments is to motivate the theoretical assumptions and bounds in Section 4, rather than argue computational feasibility or efficiency. Therefore, we think such information will be a departure from the key contributions of this paper and is better to omit.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 (e.g., preliminary or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: The paper is on theoretical advantages of temporal difference learning. We expect it to have long-term impact on many different applications in machine learning, some of which might have positive effects on society, some negative. However, since the work is currently quite distant from concrete applications, it is difficult to speculate more specifically than that.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 out 
 
 Appendix: Proof. Irreducibiliy and aperiodicity of S D implies that ν is the unique left eigenvector of S D with largest eigenvalue, λ max . Using the fact that the u(i)= E i [T ] solves (2) with R(i) = 1 for i ∈ D and R(i) = 0 for i / ∈ D, a direct calculation yields E ν [T ] = (1 -λ τ max ) -1 E ν [T ∧ τ ]. Therefore ∥(I -S τ D ) -1 ∥ ≥ (1 -λ τ max ) -1 = E ν [T ] E ν [T ∧ τ ] ≥ E ν [T ] τ and κ τ = ∥(I -S τ D ) -1 ∥∥I -S τ D ∥ ≥ E ν [T ] τ ∥I -S τ D ∥.Proof of lower bound of ∥I -S D ∥ 2 . Let ŜD be the restriction of S D to row and column indices in D, i.e. the (n -2) × (n -2) submatrix in the middle of S D . ŜD is a substochastic matrix that satisfies detailed balance with respect to p in (9) for those entries in D. Therefore, ŜD is similar to a real symmetric matrix, and all eigenvalues of ŜD are real. Let λ min be the smallest eigenvalue of ŜD .We have ∥I -S D ∥ 2 ≥ 1 -λ min .We will derive an upper bound of λ min to show that ∥I -S D ∥ 2 is bounded away from 0.Define an (n -2) × (n -2) diagonal matrix D p as D p (i, i) = p(i + 1). Note the index adjustment is due to the size difference of D p and p, and similar adjustment will persist in this proof. By the detailed balance property ŜD (i, j)p(i + 1) = ŜD (j, i)p(j + 1) for i, j = 1, . . . , n -2, the matrixA = D 1 2 p ŜD D -1 2 pis a symmetric matrix, and it has the same eigenvalues as ŜD . Now we will give an upper bound of λ min , the smallest eigenvalue of A. By Rayleigh quotient characterization of λ min , any length n -2 nonzero vector v satisfies λ min ≤ v T Av v T v . Specifically, we choose v asv(i) = 2 n -1 sin i(n -2)π n -1 , i = 1, 2, . . . , n -2.The motivation is that in the limit n → ∞, A will be related to a (weighted) finite difference matrix for the Laplace operator in one dimension, so we would like to use v which is a unit eigenvector corresponding to the smallest eigenvalue of the Laplace operator.Our remaining work is to calculate v T Av and upper bound it. A is a tridiagonal matrix with A(i, i) =P (i + 1, i + 1), A(i, i + 1) = 1/ 2 pi+1 pi+2 + pi+2 pi+1 , A(i -1, i) = 1/ 2 pi pi+1 + pi+1 pi .By direct calculation, with α = π n-1 we havev T Av = 2 n -1 n-2 i=1 1 - p i+2 2(p i+1 + p i+2 ) - p i 2(p i+1 + p i ) 1 -cos(2iα) 2 + 2 n -1 n-2 i=1 1 4 1 pi+2 pi+1 + pi+1 pi+2 [-cos α + cos((2i + 1)α)] + 2 n -1 n-2 i=1 1 4 1 pi+1 pi + pi pi+1 [-cos α + cos((2i -1)α)] .According to ( 9), e -1 ≤ |p(j)/p(i)| ≤ e for |j-i| = 1. We also have the inequality pj pi + pi pj ≥ 2. Applying these bounds and separately summing terms of cosines with positive and negative signs, we have an upper boundλ min ≤ v T Av ≤ n -2 n -1 1 - 1 1 + e - 1 n -1 (1 - 1 1 + e ) ⌊ 3 4 (n-1)⌋ i=⌈ n-1 4 ⌉ cos(2iα) - 1 n -1 1 - 1 1 + e -1    ⌊ n-1 4 ⌋ i=1 cos(2iα) + n-2 i=⌈ 3(n-1) 4 ⌉ cos(2iα)    - cos α 2(n -1) (n -2) √ e + 1 n -1 1 2 √ e ⌊ 3n-1 4 ⌋ i=⌈ n+1 4 ⌉ cos((2i -1)α) + 1 n -1 1 2    ⌊ n+1 4 ⌋ i=2 cos((2i -1)α) + n-2 i=⌈ 3n-1 4 ⌉ cos((2i -1)α)    + 1 4(n -1) i=1,n cos((2i -1)α).Using exact formulas of sum of cosines, we haveλ min ≤ v T Av ≤ n -2 n -1 1 - 1 1 + e - 1 n -1 1 - 1 1 + e sin(αa 1n ) sin α cos(αb 1n ) - 1 n -1 (1 - 1 1 + e -1 ) sin(αa 2n ) sin α cos(αb 2n ) + sin(αa 3n ) sin α cos(αb 3n ) - cos α 2(n -1) n -2 √ e + 1 n -1 1 2 √ e sin(αa 4n ) sin α cos(αb 4n ) + 1 n -1 1 2 sin(αa 5n ) sin α cos(αb 5n ) + sin(αa 6n ) sin α cos(αb 6n ) + 1 4(n -1) i=1,n cos((2i -1)α), with a 1n = 3(n-1) 4 -n-1 4 + 1, b 1n = 3(n-1) 4 + n-1 4 , a 2n = n-1 4 , b 2n = n-1 4 + 1, a 3n = n -1 -3(n-1) 4 , b 3n = n -2 + 3(n-1) 4 , a 4n = 3n-1 4 -n+1 4 + 1, b 4n = 3n-1 4 + n+1 4 -1, a 5n = n+1 4 -1, b 5n = n+1 4 + 1, a 6n = n -1 -3n-1 4 , b 6n = n -3 + 3n-1 4. Note that αa 1n , αa 4n → π 2 and αa in → π 4 as n → ∞ for all other i's. Similarly, αb in have corresponding limits. Also, (n -1) sin α → π. Based on these limits, as n → ∞, the right hand side of the inequality above also approaches a limit. Specifically in the limit,lim sup n→∞ λ min ≤ (1 - 1 1 + e ) - 1 2 √ e + ( 1 2 - 1 1 + e + 1 1 + e -1 - 1 2 √ e ) 1 π ≤ 0.64.Therefore, lim inf n→∞ ∥I -S D ∥ 2 ≥ 1 -lim sup n→∞ λ min ≥ 0.36. This shows that for large n, ∥I -S D ∥ 2 is bounded away from 0.Proof of (10). We can find an explicity formula for u by solving the linear systemEQUATION)By the symmetry of p,EQUATION)We can derive bounds based the last expression. A loose bound uses the fact that the sum is larger than the reciprocal of the smallest probability, and this probability is exponentially small.EQUATION)More carefully, for any small ε > 0, there are O(n), cos( 4π(i-1) n-1 ) terms that are smaller than -1 + ε, and for these terms, p(i) ≤ 1 3 exp( n-1 4π (-2 + ε)). Therefore,EQUATION)Proof of (11). This time u(i) solvesp(i -1) 2(p(i) + p(i -1)) (u(i) -u(i -1)) = p(i + 1) 2(p(i) + p(i + 1)) (u(i + 1) -u(i)), i = 2, 3, . . . , n -1 (19) with u(1) = 0, u(n) = 1. We find that u(2) = 1 p(1) + 1 p(2) n-1 i=1 1 p(i) + 1 p(i+1).(20)A loose bound isEQUATION)More carefully, for any small ε > 0, there are O(n), cos 4π(i-1)n-1terms that are smaller than -1 + ε, resulting in the boundEQUATION)Proof of (5) in Theorem 1 . Each entry of St -S t is a ratio of two random variables, asEQUATIONWe will prove all entries of St -S t for all 1 ≤ t ≤ τ satisfy a central limit theorem by a central limit theorem for the (normalized) numerators, and then apply Slutsky's theorem to include the denominators. By an argument similar to the one used to establish Lemma 1 inThiede et al. [2015] , u is a differentiable function of entries of S t . The delta method, therefore, transforms a central limit theorem for these entries into a central limit theorem for u.Let M t denote a matrix containing only the (normalized) numerators of St -S t , that is,M t (k, ℓ) = 1 M M j=1 1 {k} (X j 0 ) 1 {ℓ} (X j t∧T j ) -S t (k, ℓ) .Let M 1:τ represent a long vector formed by flattening out each matrix M t in row major order and gluing up in time order. Then, since trajectories are independent, M 1:τ satisfies a central limit theorem asEQUATION)For convenience, letΣ 1:τ M ((t 1 , k 1 , ℓ 1 ), (t 2 , k 2 , ℓ 2 )) denote the entry of Σ 1:τ M that records the covariance Cov 1 {k1} (X 0 ) 1 {ℓ1} (X t1∧T ) -S t1 (k 1 , ℓ 1 ) , 1 {k2} (X 0 ) 1 {ℓ2} (X t2∧T ) -S t2 (k 2 , ℓ 2 ) .(25) Before explicitly calculating this covariance, we deal with the denominators first. Let μ be the vector containing all the (normalized) denominators, that is, μ(k) = 1 M M k . Then, again because of independence of trajectories, we have a weak law of large numbers asEQUATIONwhere we recall that µ is the initial distribution supported on D, and P -→ means convergence in probability.As for Σ 1:τ M , the key fact is that 1 {(k,ℓ)} for different k are independent. Therefore,EQUATION)Combining ( 23), ( 24), ( 26) and ( 27), by Slutsky's theorem, we obtain a central limit theorem for S asEQUATIONwhere S1:τ and S 1:τ are vectors flattened out from St and S t for 1 ≤ t ≤ τ with the same order as in M 1:τ , andEQUATION)According to ( 25) and ( 27),Σ 1:τ ((t 1 , k 1 , ℓ 1 ), (t 2 , k 2 , ℓ 2 )) = 0 for k 1 ̸ = k 2 , Σ 1:τ ((t 1 , k, ℓ 1 ), (t 2 , k, ℓ 2 )) = 1 µ(k) E k 1 {ℓ1} (X t1∧T ) -S t1 (k 1 , ℓ 1 ) 1 {ℓ2} (X t2∧T ) -S t2 (k 2 , ℓ 2 ) .(30)To transform the central limit theorem (28) to a central limit theorem of ũ(i), we point out that u(i) is a differentiable function of entries of S t and now we are going to calculate these derivatives. Entries in u outside of D are fixed under any perturbation in S t . To write down an equation satisfied by all entries of u, we rearrange (2) intoEQUATIONwhereR D c (i) = 1 i∈D c R(i) for i ∈ [n]. R D c is a vector whose nonzero entries are those fixed boundary values of u. Because S t is a stochastic matrix, we consider it to be determined by off diagonal entries asEQUATIONThis implies thatEQUATIONFor a specific pair (k, ℓ) with k ∈ D and ℓ ̸ = k, we define S t (ε) := S t + ε(e k e T ℓ -e k e T k ). Then we define∂u ∂S t (k, ℓ) (S t ) := ∂u 1 ∂S t (k, ℓ) (S t ), . . . , ∂u n ∂S t (k, ℓ) (S t ) T = d dε u S t (ε) ε=0 .Differentiating (31) with respect to ε and taking care of (33), we find the derivative with respect to S t (k, ℓ) for different k, ℓ, t. The formulas are different for different t. For t = τ , k, ℓ ∈ D, we haveEQUATIONInstead, for k ∈ D, ℓ ∈ D c , taking derivatives leads to(I -S τ D ) ∂u ∂S τ (k, ℓ) -e k e T k u = e k e T ℓ R D c ,which gives the same formula for ∂u ∂S τ (k,ℓ) as in (34) after rearranging using the fact thatEQUATIONNow, we can use the delta method to transform (28) to a central limit theorem for ũ(i)EQUATIONwithσ 2 i = k1,k2∈D, ℓ1,ℓ2∈[n], k1̸ =ℓ1,k2̸ =ℓ2 τ t1,t2=1 ∂u(i) ∂S t1 (k 1 , ℓ 1 ) ∂u(i) ∂S t2 (k 2 , ℓ 2 ) Σ 1:τ ((t 1 , k 1 , ℓ 1 ), (t 2 , k 2 , ℓ 2 )) = k∈D 1 µ(k) e T i (I -S τ D ) -1 e k 2 E k         ℓ∈[n] ℓ̸ =k (R D (ℓ) -R D (k)) τ -1 t=1 (1 ℓ (X t∧T ) -S t (k, ℓ)) + (u(ℓ) -u(k))(1 ℓ (X τ ∧T ) -S τ (k, ℓ)) 2 = k∈D 1 µ(k) e T i (I -S τ D ) -1 e k 2 E k     ℓ∈[n] R D (ℓ) τ -1 t=1 (1 ℓ (X t∧T ) -S t (k, ℓ)) + u(ℓ)(1 ℓ (X τ ∧T ) -S τ (k, ℓ)) 2 = k∈D 1 µ(k) e T i (I -S τ D ) -1 e k 2 E k   τ -1 t=1 R D (X t∧T ) + u(X τ ∧T ) -(u(k) -R D (k)) 2   = k∈D 1 µ(k) e T i (I -S τ D ) -1 e k 2 E k   τ -1 t=0 R D (X t∧T ) + u(X τ ∧T ) -u(k) 2  .(37) The second equality is obtained by plugging in ( 35), ( 34) and (30). The third equality uses the fact thatℓ∈[n] 1 ℓ (X t∧T ) = ℓ∈[n] S t (k, ℓ) = 1, for any k ∈ D, t ≤ τ.The fourth equality uses the Bellman equation ( 2). Now we introduce the key lemma for Theorem 1. The lemma characterizes the continuity of the operator E ℓ T t=0 1 {j} (X t ) in terms of the initial state ℓ. Note that a dot product of this operator with the corresponding reward R(j) generates the value function u(ℓ).We define hitting times counting from t = 0. That is, Tk = min{t ≥ 0 : X t = k}. This differs from T k because Tk includes t = 0. Similarly, we define T τ k and more generally TA and T τ A for any subset A ⊆ [n] as the counterparts of T τ k , T A , and T τ A but counted from t = 0. But notice that we have defined T and T τ to be counted from t = 0. In all hitting time definitions, when the set over which the minimum is taken is empty, the hitting time is defined to +∞.EQUATIONProof of Lemma 2. The proof will proceed by representing all quantities by probabilities, and then with the help of a complementary Markov chain, we can bound the difference of involved probabilities. We start with two basic identities that hold for any i, k ∈ D,EQUATIONandEQUATIONNote that when j ∈ D c , P j [T ≤ T j ] = 1. With ( 39) and ( 40), the left hand side of (38) becomesEQUATIONTo make probabilities related to X t in (41) become probabilities related to τ -step transitions, we consider another Markov chain Y τ,j t that follows the transition probability matrix S τ j := (S j ) τ , where S j is defined asEQUATION)S j is the same as S except it is stopped once j is hit. Note that when j ∈ D c , S j = S. Define hitting times T τ,j k , T τ,j and T τ,j k of Y τ,j t similarly as those of Y τ t . If Y τ,j t hits j before k, then T τ,j k = +∞, and this exception is similarly defined for other hitting times. Note that T τ,j counts from t = 0 as does T . One key relation between Y τ,j t and X t∧T is thatEQUATIONThis relation is guaranteed by the fact that Y τ,j t will stay at j if a coupled X t∧T hits j at any time within each length-τ time interval. Now consider the case where ℓ ∈ D, j ̸ = k and j ̸ = ℓ, and identify all of D c \ {j} with a single additional index ∆. Note that whether j ∈ D or j ∈ D c ,EQUATIONConsider another Markov chain Z t ∈ {ℓ, k, j, ∆} that records transitions only when Y τ,j t transitions between one of these states. We will use Q to denote the transition probabilities of Z t . For example,Q(ℓ, ℓ) = P ℓ [Z 1 = ℓ] = P ℓ T τ,j ℓ < min{T τ,j k , T τ,j j , T τ,j ∆ } and Q(ℓ, k) = P ℓ [Z 1 = k] = P ℓ T τ,j k < min{T τ,j ℓ , T τ,j j , T τ,j ∆ } .In fact, P ℓ T τ,j j < T τ,j ∆ and P k T τ,j j < T τ,j ∆ satisfy the linear systemEQUATIONIt is convenient to work with the normalized transition probabilitiesQ(ℓ, •) = Q(ℓ, •) 1 -Q(ℓ, ℓ) and Q(k, •) = Q(k, •) 1 -Q(k, k) .With this notation, solving (45) reveals the identitiesP ℓ T τ,j j < T τ,j ∆ = Q(ℓ, k)Q(k, j) + Q(ℓ, j) 1 -Q(ℓ, k)Q(k, ℓ)andP k T τ,j j < T τ,j ∆ = Q(k, ℓ)Q(ℓ, j) + Q(k, j) 1 -Q(ℓ, k)Q(k, ℓ) ,from which, after a little more algebra, we find thatEQUATION)This is the key quantity that characterizes the difference between probabilities with initial states k and ℓ. By bounding this, we can finally get relative variance bounds. We observe immediately thatQ(ℓ, ∆)Q(k, j) 1 -Q(ℓ, k)Q(k, ℓ) ≤ P k T τ,j j < T τ,j ∆ Q(ℓ, ∆).Now we relate these probabilities to Y τ t . We have thatP k [T τ ℓ < T τ k ∧ T τ ] ≤ Q(k, ℓ) + Q(k, j), so Q(k, ℓ)Q(ℓ, j) + Q(k, j) P k [T τ ℓ < T τ k ∧ T τ ∆ ] ≥ Q(k, ℓ)Q(ℓ, j) + Q(k, j) Q(k, ℓ) + Q(k, j) ≥ Q(ℓ, j).This yieldsQ(k, ∆)Q(ℓ, j) 1 -Q(ℓ, k)Q(k, ℓ) ≤ P k T τ,j j < T τ,j ∆ Q(k, ∆) P k [T τ ℓ < T τ k ∧ T τ ].Bringing these inequalities back into (46), with ( 43) and ( 44) we haveP ℓ Tj ≤ T -P k Tj ≤ T ≤ P k T τ,j j < T τ,j ∆ max Q(ℓ, ∆), Q(k, ∆) P k [T τ ℓ < T τ k ∧ T τ ] . Now notice that P k [T τ < T τ k ] ≥ Q(k, ∆) + P k [T τ ℓ < T τ k ∧ T τ ] Q(ℓ, ∆), and therefore,EQUATIONPlugging (47) back into (41) we find thatEQUATIONBy ( 40) and the definition of Q τ (k, ℓ) in Theorem 1, this is the stated bound in the case where ℓ ∈ D, j ̸ = k and j ̸ = ℓ.Now we deal with the exceptional cases. When ℓ ∈ D but j = k or j = ℓ, the same conclusion holds with minor modifications of the intermediate steps. Specifically, take j = ℓ (so that j ∈ D and ∆ = D c ) as an example. Then Z t ∈ {ℓ, k, ∆} records transitions of Y τ,j t among these three states, with Q denote its transition probabilities.P ℓ T τ,j j ≤ T τ,j -P k T τ,j j ≤ T τ,j = 1 -Q(k, j) = Q(k, ∆),andP k [T τ ℓ < T τ k ∧ T τ ] = Q(k, j), P k [T j < T ] = Q(k, j). Therefore, P ℓ Tj ≤ T -P k Tj ≤ T ≤ P k [T j < T ] Q(k, ∆) P k [T τ ℓ < T τ k ∧ T τ ].Then the following steps are the same as (48) in the general case.When ℓ ∈ D c , j ∈ [n] and ℓ ∈ ∆, P ℓ Tj ≤ T = 0.P i T τ k < T τ P k [T τ < T τ k ] P ℓ Tj ≤ T -P k Tj ≤ T P j [T ≤ T j ] = P i T τ k < T τ P k Tj ≤ T P k [T τ < T τ k ] P j [T ≤ T j ] ≤ P i Tj ≤ T P j [T ≤ T j ] P k T τ ℓ < T τ k ∧ T τ D c \{ℓ}.Applying (40) to the right hand side, this gives the bound (38).When ℓ ∈ D c and j = ℓ, P ℓ Tj ≤ T = 1. We again use Q to record transitions of Y τ,j t (= Y τ t ) among {k, j, ∆}. Then,P i T τ k < T τ P k [T τ < T τ k ] P ℓ Tj ≤ T -P k Tj ≤ T P j [T ≤ T j ] ≤ P i T τ k < T τ P j [T ≤ T j ] P k [T τ < T τ k ] ≤ P i Tj ≤ T P j [T ≤ T j ] P k T τ ℓ < T τ k ∧ T τ D c \{ℓ} .The last inequality follows from the facts that1 P k [T τ < T τ k ] = 1 1 -Q(k, k) = Q(k, j) Q(k, j) = P k T τ j ≤ T τ P k T τ ℓ < T τ k ∧ T τ D c \{ℓ} .We thus prove that the bound (38) holds for any indices i, k, j ∈ D, ℓ ∈ [n] and k ̸ = ℓ.Now we are well prepared to prove (6) in Theorem 1.Proof of (6) in Theorem 1. We will interpret two main terms in (5) probabilistically. First, for i, k ∈ D,EQUATION)As for the expectation following e T i (I -S τ D ) -1 e k in (5), we note from the fourth equality in (37) thatE k τ -1 t=0 R D (X t∧T ) + u(X τ ∧T ) -u(k) 2 = Var k τ -1 t=1 R D (X t∧T ) + u(X τ ∧T ) ,where the subscript k indicates conditioning on X 0 = k. Since this is a variance, we can decompose it into conditional variance of each step by the law of total variance, asEQUATION)By the Bellman equation ( 2), Eτ -1 t=1 R D (X t∧T ) + u(X τ ∧T ) X 0 = k, X 1∧T = u(X 1∧T). And the first term can be simplified asE k Var τ -1 t=1 R D (X t∧T ) + u(X τ ∧T ) X 0 = k, X 1∧T =E k Var τ -1 t=2 R D (X t∧T ) + u(X τ ∧T ) X 0 = k, X 1∧T, and then we can further condition it on X 2∧T and perform a similar decomposition as in (50). This conditioning can be done inductively for X t∧T up to t = τ . As a result of this inductive conditioning, we obtainEQUATIONFor the inequality, we use the property of variance thatE k (Var X (t-1)∧T (u(X t∧T ))) ≤ E k (E X (t-1)∧T (u(X t∧T ) -u(k)) 2 ) = E k (u(X t∧T ) -u(k)) 2 .Now, we further decompose the difference u(ℓ)-u(k) into components that we have already bounded in Lemma 2, using the fact that R is nonnegative throughout our paper.EQUATIONThen according to Lemma 2, we can bound the variation in u between states asE i T τ -1 t=0 1 {k} (Y τ t ) |u(ℓ) -u(k)| ≤ j∈[n] E i T t=0 1 {j} (X t ) R(j) Q τ (k, ℓ) = u(i) Q τ (k, ℓ) .Combined with ( 49) and ( 51), this yieldsσ 2 i ≤ u 2 (i) k∈D 1 µ(k) τ t=1 S t (k, ℓ) Q τ (k, ℓ) 2 .As for Corollary 1, the strengthening comes from an intermediate step in the proof of (6).Proof of Corollary 1. If R(i) = 0 for any i ∈ D (for example, when u is the committor function), thenEQUATIONCompared with (51), we see that the same following steps will replace t S t (k, ℓ) in Theorem 1 by S τ for Corollary 1.Justification: In Section 1.1, we state the linear system for the estimator. In Section 3, we state the detailed setting of the experiments. The readers should be able to reproduce experimental results using the information. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may 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 is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to 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.General MRPs include a discounting factor γ ∈ (0, 1]. We choose γ = 1 and assume that u is well-defined under this condition. In general, smaller values of γ make the prediction problem easier. 


Decision: This paper presents a strong theoretical contribution to the field of policy evaluation under rare events, particularly in the context of Markov chains. 
The originality of the problem, the rigor of the analysis, and the clarity of the presentation (as noted by one reviewer) make it a valuable contribution. 
The authors' rebuttal effectively addresses concerns about the numerical experiments, clarifying that empirical results do support the theoretical claims and enhancing the connection between theory and practice.

Reviews: review: paper_summary: paper_summary: This paper provides a rigorous sample complexity comparison between MC sampling and LSTD method, and shows that for rate event, LSTD can provide relatively accurate estimation with a much smaller dataset compared to MC sampling. This contradicts to the intution from the classical worst perturbation bounds.
strength_weakness: strength_weakness: - There is no simulation results for rate event scenario

- The writing can be more polished. Some explanation can be more formal. For example, it would be great if the authors can formalize their discussion in section 1.2.
questions: questions: NA
limitations: limitations: NA
paper_summary: paper_summary: The authors consider the problem of efficiency comparison between temporal difference (TD) and Monte Carlo (MC) methods for learning value functions (policy evaluation) especially in conditions involving rare events. The authors identify two challenges in policy evaluation with respect to rare events - long timescales of the rare event and need for relative accuracy in estimates of very small values. For their analysis, the authors choose the LSTD algorithm and upper bound its relative asymptotic variance. Using this bound they establish the better efficiency of TD versus MC methods in the presence of rare events. Specifically teh authros define rare events in terms of escape from a given set of states in a Markov reward process.
strength_weakness: strength_weakness: The authors compare LSTD and MC methods for policy estimation in the presence of rare events, but do not present any numerical experiments to illustrate their claims. It is not clear how the results of this paper can be practically used.
questions: questions: 1. What do the authors mean by "appropriate choice of reward function" in the statement in line 49: "Rare events can be embedded in such a formulation either as “escape from D,” or as “escape from D in an unusual way,” by appropriate choice of the reward function."
2. Is $T$ a terminal time value for the process as given in equation (1)? Is it assumed that the process ends as soon as the trajectory leaves the set $D$?
3. How does $u(i)$ reflect/determine a rare event? Can't two states resulting in two trajectories - one with a rare event and one without have the same value $u$?
4. Can the authors elaborate this point in line 68: "The MC estimator does not allow finite values of $\tau$ (unless $T$ is bounded by a constant).". Will this point change in discounted return settings?
4. $S$ is used in footnote 1, but defined later. Can the authors fix this?
5. How have the authors addressed the bias-variance tradeoff in TD vs MC methods?
6. As per the expressions given after line 87, are all states $i \notin D$ stationary states?
7. I did not understand the experiments given in Section 3. Don't escape events need to be observed in both TD and MC cases for the algorithm to evaluate the value function accurately? Don't TD and MC only vary in their ability to generalize as TD makes a Markovian assumption, while MC does not? Do the examples mainly illustrate this point?
8. What errors does the minorizing step in Section 4 introduce?
limitations: limitations: The authors mention the limitations in their work as points in different sections but do not provide a separate section only discussing these.
paper_summary: paper_summary: The paper studies the estimation of rare event statistics in discrete-time, discrete-state Markov chains. It shows that when the transitions probabilities of the chain satisfy certain locality assumptions then temporal difference estimators are exponentially more efficient than Monte-Carlo estimators. Concretely, under these assumptions, the variance of the TD estimator scales as $n^3$ in the number $n$ of states of the Markov chain, whereas the variance for MC estimators scales as $e^n$.

The proofs are accompanied by two numerical examples that provide intuition and illustrate the applicability of the theory to mean first passage time and committor function computation. They also provide an additional validation of the theoretical results.
strength_weakness: strength_weakness: The problem of rare event estimation is essentially a statistics problem, and the results seem more typical of a probability or statistics journal paper than a machine learning conference.
questions: questions: No questions at this point.
limitations: limitations: In general, the theoretical nature of the paper and clear exposition make most of the limitations appear clearly in the statements of the theorems.

Comments: comment: Thanks for these clarifications. Based on these I am increasing my score.
We thank you again for the opportunity to respond to your questions.

1. Our claim is that TD can be much more efficient than MC for problems involving rare events. The values of $u$ alone do not reveal whether the estimation problem is difficult. Imagine a process $X_t$ that always exits $D$ by the same sequence of steps ($X_t$ is deterministic). In this case the accumulated reward will not be random and we can tune the values of $u$ by our choice of $R$. Yet the MC estimator will have zero variance. So the distinguishing characteristic of the rare event setting is the difficulty of estimating $u$, and not just the values of $u$. The notion of relative accuracy may be contributing to confusion here. The size of $u(i)$ does affect how much variation in the estimate of $u(i)$ we are willing to accept. We need that variation to be small compared to the value of $u(i)$. 
2. As stated in our response to Question 8, “TD **does** require escape events in its data set” and, in our numerical examples, a small fraction of trajectories **do** escape before time $\tau$. If the data set does not include escape events, the linear system defined in Eq. (2) will be indefinite and the TD estimator will be undefined. Our Assumption 1 and the large data limit ($M \to \infty$) in our theorems guarantee the existence of escapes.
3. The large statistical error of the MC estimator in the finite state setting translates immediately to continuous spaces, and implies large estimation errors for standard ML rare event prediction schemes that use data sets of full escape trajectories. The Markov state model (MSM) approximations mentioned at lines 144-153 solve continuous space problems by first partitioning state space (usually by data clustering) and then approximating the solution to the Bellman equation by a function that is constant on each partition. Subject to the assumptions of Section 4, our theory describes the estimation error of such a scheme in the rare event setting, but does not address approximation error. We mention this briefly at lines 34-42. 

    We comment on more elaborate generalizations to continuous state spaces in the conclusion (lines 337-341). Our proof of Theorem 1 is based on new perturbation bounds for finite dimensional linear systems which, we believe, have appropriate extensions to infinite dimensional settings. Such a result would say that rather large perturbations of the operator are possible without large errors in the solution to the linear system, as long as the perturbations are “local” (as represented in the finite setting by Assumptions 2 and 3) in some appropriate sense. Once we have an infinite dimensional perturbation bound of this type, we can begin to analyze both the approximation error and estimation error of TD approximations in continuous spaces. 

4. On Line 203 we define the set $D$ as $[n] \setminus \\{1, n\\}$ for all the examples in Section 3. So $D^c$ is $\\{1,n\\}$ and a trajectory that escapes must reach either state 1 or state $n$ (the left or right boundaries). The definition of $u(i)$ in Eq. (1) only depends on the path of $X_t$ until it reaches $D^c$. It does not depend on what the process might have done after that. In our theoretical setup, every trajectory in the data set is initialized as an independent draw from some distribution $\mu$ (the uniform distribution in the numerical examples of Section 3). So our estimators (both MC and TD) also do not depend on the path of the process after reaching $D^c$. 

    As mentioned at lines 63-65, in some application settings it is common to analyze short trajectories corresponding to pieces of a single, much longer trajectory. In this case, after escaping from $D$ one must wait for the process to re-enter $D$ before gathering new data. Short trajectories gathered in this way will be correlated and, as we mention there, our analysis does not immediately apply. Looking beyond your question a little, inspection of our results does reveal some interesting, and practically important, implications for that setting. Examining the asymptotic variance formula in Eq. (5), we see that small values $\mu(k)$ can result in large errors. In fact, if we replaced the uniform initial distribution used in Sec. 3 by the invariant distribution given in Eq. (9) (which does not satisfy Assumption 1), then TD would have exponentially large relative variance. But a single very long trajectory would result in points drawn approximately from this invariant distribution. The implication is that a practitioner either needs to generate data using a different strategy (as has been emphasized in several references cited at lines 31 to 33), or, if that is not possible, reweight the data. This topic is important and we hope to focus on it more in follow up work.
I thank the author for patiently answering all my queries. However, I still have some questions: 
1. Confusion regarding $u(i)$: Can a rare event be identified using $u(i)$ or is the claim restricted to better estimation of $u(i)$ even in the presence of rare events?
2. In your response to my earlier Question 8, you say that "TD does require escape events in its data set.". However, if there are no such events in the dataset, how will the TD estimator learn the values correctly?
3. While I understand that this paper is restricted to the finite MDP setting, do the authors have any thoughts on how their analyses and conclusions hold true in the function approximation based setting with large and possibly continuous state and action spaces?
4. Sorry for asking this again, but I have a slight confusion here. In the examples in Section 3, what does escape from Set D imply? What is set D in each of these examples and where does the trajectory that escapes from D go? 

I am satisfied with the other responses and accordingly am increasing my score.