The surprising efficiency of temporal difference learning for rare event prediction
Authors: Xiaoou Cheng
Jonathan Weare
Venue: NeurIPS 2024 poster (2024)
Keywords: temporal difference learning
reinforcement learning
rare events
policy evaluation
prediction
perturbation bounds
Primary area: reinforcement_learning
TL;DR: Temporal difference methods require exponentially less data than Monte Carlo to estimate rare event statistics

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.

The surprising efficiency of temporal difference learning for rare event prediction
Xiaoou Cheng
Jonathan Weare
Courant Institute of Mathematical Sciences
Courant Institute of Mathematical Sciences New York University New York, NY 10012
New York University
New York, NY 10012
chengxo@nyu. edu
weare@nyu.
Abstract
We quantify the efficiency of temporal difference (TD) learning over the direct, Monte Carlo (MC), estimator for policy evaluation in reinforcement learning, with 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 relative accuracy in estimates 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 central limit theorem for the L.TD estimator and upper bound the relative asymptotic variance by simple quantities characterizing the connectivity 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 error the MC estimator are exponentially large in the number of states, LSTD maintains fixed level of relative accuracy with a total number of observed transitions of the Markov chain that is only polynomially large in the number of states.
Introduction
Prediction of the future behavior of dynamical system from time series observations is fundamental task science and engineering. One need only remember the weather forecast consulted this morning to appreciate the substantial intersection this problem has with everyday lives. Beyond its obvious importance, prediction is also key component in modern machine learning tasks like reinforcement learning, where the rules governing the dynamical system adjusted optimize some reward. Exciting applications 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 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 rypical 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 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 al.) 2021 Lucente al.
2021 Finkel et al. 2023a Strahan et al. 2023a
Jacques- Dumaas et al. 2023 Strahan et al. 2023b
Guo et al. 2024].
Within the context of reinforcement learning, "prediction" refers to policy evaluation, that is, cal- culation of the value function of states given a policy [Sutton and Barto 2018). Prediction is the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 projec- tion onto a finite state Markov process (Thiede et al. [2099] Finkel et al. [202]] 2023a Jacques- Dumas itt 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) (. R), where [n] = {1, 21....... n) is the state space, P is the Markov transition kernel with i]. and R is a deterministic, non-n non-negative reward function. Time
P(i.j) P 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 form
T
(i1) E,
Σ R(X,)
(I)
where D a subset of [n], T = min 0: Xx & D} is the escape time from D, and the subscript i on the expectation indicates that Xo = 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.
1.1 Monte Carlo and temporal difference learning
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 the central role of the escape event from D in (T). We are specifically interested in cases in which E, [T] can be very large so that the length of single escape trajectory can be very large, and/or cases in which large values of the reward functions are very unlikely so that can be very small.
Our task is to learn an estimate of from set of M samples (X),X;, Xf....,. ....... X Xo, Xx........, XYAT with { drawn from some (possibly unknown) initial probability dis- tribution f 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 r trajectories can be harvested from a single longer trajectory. Here, to simplify the analysis, we assume that the trajectories are drawn independently.
TATe Fe=1 of
The most direct estimator of uii) is the Monte Carlo (MC) estimator
M. T
1
a(i)
R (x:). when M, > 0,
M,
(=1
1=0
where M, is the number of samples with X i, i.e. M, = EM (()
(Xf). The estimator is undefined for i D with M, O. The MC estimator does not allow finite values of 7 (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.. 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 uui) > O, control of the relative variance, Var [ū(i]] /u² (i), often requires M x 1/ul (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 the solution to certain Bellman equation [uttonn] 1988). They enforce temporal local consistency of the estimate of the value function.
GGeneral MRPs include a discounting factor E (0, 1]. We choose 7 = and assume that u is well-defined under this condition. In general, smaller values of make the prediction problem easier.

---

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. s oc). TD schemes are used heavily in reinforcement learning and they are often observed to out-perform MC (Sutton and Barto 2018 However, 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 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 in ① solves the linear system
(1 (T)(i) = Σ RDi( for D and u(i) R(i) for D
(2)
1=
where
- for fo and S(i.j) = 6.g for i D,
is the transition operator of XAAT, S is the 7th power of S and RD(1) R(i) for i E D while RD( = 0 for i & D. In the limit - oc, (2) becomes (T). In our theory and examples, we will see that the choice of r can have a dramatic effect on the performance of the estimator.
TD methods estimator in this tabular setting is the solution to a linear system where the transition matrix $ in (2 is approximated with trajectory data. We set 5 and, for =
trajectory data to find approximate solution to 2 Specifically, the LSTD
M Σ
(11,,))
(05)) (x, Xlrrs) for M; > 0 and (i,5)) 5.3 for M, 0.
M, t=1
Unlike St, 3t are not powers of single matrix. When it exists, the 7-step LSTD estimator, ū solves
(I (-
Σ Rn(i) for e D and ū(i) R(i) for $ D.
(Like the MC estimator, ū(t) is undefined when M, 0). In the limit, the 7-step LSTD and MC estimators are equivalent. We therefore occasionally refer to the Monte Carlo estimator as the 7 oc estimator.
1.2 Our contributions
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 u, the solution to (3). Clearly (3) only requires
access to trajectories of length r, but how sensitive is the solution of 2 perturbations in S? If it is very sensitive then any reduction data requirements from shorter trajectories may be offset by need for many more trajectories. Classical perturbation theory tells us that errors St 5' can, in the worst case, be amplified in 7 by factor of the condition number x = ||(T -D) -|]| Sbll. where 5%, the matrix obtained from S by setting to zero any row or column with index in D [emmell 1997]. As the next lemma shows, when typical values of T are much larger than "I will be very large. The proof of Lemma iis in Appendix A
Lemma 1. For any consistent matrix norm, if the restriction of Sp to row and column indices in D irreducible and aperiodic, then [[(T ((=-
[ where v(i) = lim P [X, i f] the quasi-stationar distribution and the subscript on the expectation indicates that Xo drawn from [See/Collee et al. (2012) for more about the quasi-stationary distribution).
While it is possible that a small value of - S ll can compensate for a large value of [T(T//r and result in 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 || Sp is bounded away from zero even the escape event becomes increasingly rare (see Appendix B).
Thus it would seem that we are forced to choose between two doomed options: choose 7 small to control the length of trajectories need to observe but observe huge number (M x E,, (T)TT) of
3

---

them to drive down the error in S² or observe very long trajectories (r x [T]) to control k². 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 few simple and practically relevant assumptions we will be able show that 7-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 of / where of is the variance of the limiting normal distribution in a central limit theorem for ū(i) established in Theorem I Also in Theorem | we provide 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 x², 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 however, the relative asymptotic variance of the LSTD estimator scales, worst like n²"
1.3
Related work
Since it first appeared in [Sutton 1988), there have been numerous variants of TD Bradtke and
Barto 1996 Dann et al., Lillicra 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 T Siitsiklis and Van Roy 1997). along with examples of divergence [Baird 1995
Tsitsiklis and Van Roy| [997]. More recently, nonasymptotic convergence analysis of TD has been
performed [hhandari al. [2018 Dalal et al. 2018 Srikant and Ying 2019 Cai et al. 2019).
Besides own convergence, a long-considered question for TD when and how outperforms MC. While practical experience suggests that TD is more efficient than MC, a comprehensive theory is lacking. Grunewalder 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. [heikki 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 (usii and Pande 2018) and dynamic mode decomposition methods [Schmid] [022] 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 [Thieee et al. [019 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
al. 202 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.
1.4 Notation
x 2, NN o indicates that a random variable X converges in distribution to a normal distribution with mean Po and variance o.. For any subset A C [n)) we define the hitting time Ta = min(t > 0: X, E A}. When X, never hits A, TA = Doc. When the set A contains only one state i, we use T; for simplicity. Note that in ④ T counts from = 0 instead. While S is the transition probability matrix for the Markov chain XLAT we define another Markov chain Y," whose transition probability matrix is S². For Y,,, we define its hitting time to be T = min(t > 0 Y! E A). We define T = min 2 0 Yr E D) as counterpart of T for X.. We use e; for the ith standard basis vector, i.e. e4()) = dij- For any two quantities a and b, a b means that there exists a positive constant C' independent of such that 2 Cb. Similarly, S b means that S Cb.
4

---

2 An upper bound for relative asymptotic variance
As previous authors have done [Cheikhi and Russo 2023 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 (ut)= > O for all i E D and P is irreducible. Then, as the number of samples M o0,
VM (ū(1) u(i)) 2, NN(0,07)) of)
with
- (1 -ex En
Σ
RD (Xar)) + -(XxAAT)-ule (5)
KED u(k) Moreover, the relative asymptotic variance o satisfies the upper bound
L(=0
En S*,Ks (k,
Σ
(6)
RED, RE(n).
where we have introduced the key quantity (kk = P& T7 <TAATON
An important special case that will include one of the examples studied in Section occurs when the reward function zero in D (but non-zero in D*). In this case we can strengthen the bound in Theorem by only including ST in the numerator.
Corollary 1. Under the same assumptions as in Theorem
7 Tbut with R(i) for any E D,
ST (k,k)) E)
Σ
u2
m(k) (k,
8E(n), Egp
Let us take a moment to parse the bounds in Theorem and Corollary The bounds tell us that if the sum 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 E). In particular Q" (Is, () 2 ST (k E). While the probability Q" (kc E) can be very small for most pairs (k,, E), evidently it is the size of Q" (k, E)2 relative to St (k, E) for S T (or only ST (kc, E)) that matters. Fortunately, in many cases, we can expect Q' (k: 8)2 to be much larger than S (k, E) for a good choice of r. We will quantify this statement in the rare event setting in Section 4
quantity very similar to Q" (ks, E) appears in the matrix analysis literature Thiede al. 2015
measure of the sensitivity of the relative accuracy of the invariant distribution of Markov chain to entry-wise perturbations in its transition probability matrix. The proofs of Theorem I and Corollary [ 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.
3 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 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
Both problems are based on a one dimensional nearest neighbor chain X, E [n] with transition rules
p(i +1)
P(i + = 2(p(1) + +pi +(p 1)) and P(i, = 1 i + + - P(i, i - 1) for i E [n] (8)
5

---

with P(1,0) P(n,
+ n
= O on the boundary. Here is the invariant probability vector of P.
4 71 1
p(i) x exp
cos
4T
which has modes around i 1. (n + 1)/2. and i n. that become more sharply peaked as increases. The escape time from any of these modes scales exponentially with n. We will be interested in predictions related the escape of X, from D [n] [1, and choose μ be the uniform distribution on D.
Before moving the specific problem statements, point out that despite the exponentially long waiting time to transition between the modes of p. transitions between nearest neighbor states remain stable increases. In fact, for E D, i 1) 2 2[++]] Stable local transition probabilities
such these play key role in our upper bounds in Section where they are used to lower bound (k, E) in (6)
The mean first passage time. The mean first passage time u(i) = [T] solves (2 with R(i) = for i E D and R(i) = 0 i & D. We plot the mean first passage time for n 20, 40, and 80 in the left panel of Fig. Evidently the largest values of [ scale exponentially with In Appendix B we prove that, near i = (n 1)/2.
3n 8T
E
T exp
(10)
Therefore the trajectories required by the MC estimator will include a number of transitions of X that scales exponentially with n. We compare the performance the MC estimator of the mean first passage time to that of the LSTD estimator, u, found by solving with r = 1. In the middle panel of Fig. I we plot the relative asymptotic variance, o²/u²(i). for the same values n. the same panel we plot empirical estimates of the the (non-asympootic) relative mean squared error (MSE), MMSE [ū(i]] / (i), with M 10n 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². Meanwhile, near the boundary of D, the relative MSE of the MC estimator (computed exactly) grows exponentially fast with n, can be seen in the right panel of Fig.
Mean First Passage Time
10
(relative MSEUh"3
20
40
(relativee MSEUI"S
n- 80
2
time
10a
0.50
0.50
(-130n-1)
(-1Win-1)
(-11jn-1)
Figure 1: Left: the (exact) mean first passage time u(i) with = 20, 40, and 80. Middle: the relative asymptotic variance (solid lines) and the relative empirical MSE (circles) of the LSTD estimator with 1. The relative empirical MSE are obtained with sample sizes M 10n3. Right: the (exact) relative asymptotic MSE of the MC estimator.
The committor. We now consider estimation of the committor function
u(i)) = P Tr Ti] for i E [n] (1, and u(i) 1 (i) for [1,n].
The committor corresponds to the choice R(i) = for * n and R(n) = 1. Because E, [T] can be exponentially large, the MC estimator of the committor again requires data set containing expo- nentially long trajectories of X,. Moreover, in Appendix B we prove that ui) can be exponentially small in n1
(2) S cxp
n 4
(11)
as is evident in the plot of the committor for = 20, 40, and 80, in the left panel of Fig. As consequence, the relative MSE of the MC estimator, plotted in the right panel of Fig. 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 r grows more slowly than n². Again empirical estimates of the relative MSE of the LSTD estimator with M = 10m agree well with corresponding relative asymptotic variances and show the same trend.
Committor
16
probabiiity
2
trelaative MSEIing
0.10
trelative MSED
16a
0.08
10-3
10"4
0.06
10
10aa
0.04
10"
0.02
10
0.00
0.00
0.50
0.75
1.00
0.50
(-110n-11
(:11Vnn11
(-1Min-1)
Figure 2: Left: the (exact) committor function uii) with n = 20, 40, and 80. Middle: the relative asymptotic variance (solid lines) and the relative empirical MSE (circles) of the LSTD estimator with T == 1. The relative empirical MSE are obtained with sample sizes M 10n Right: the (exact)
relative asymptotic MSE of the MC estimator.
Together, the mean first passage time and the committor estimation problems in this section strongly suggest 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 r = 1. In practice, the best choice of is long enough to avoid nearly diagonal S7, but not so long as to lose the efficiency advantage of TD over MC that we have just observed. Our bounds in Theorem T also change with т. To better illustrate the effect of 7 on the relative asymptotic variance of the LSTD estimator and on our bounds, we now consider "lazier" version of the Markov chain in (8. Specifically,, we define P(i, 1) = To(p((++p(E))) for i E D, with the same boundary
p(i=l)
conditions as before. We again consider estimates of the mean first passage time and the committor, now with fixed 40. We plot the maximum of the relative asymptotic variance, of //²(()), over i E D in Fig. 3 along with the bound (6) for the mean first passage time in the left panel and (7) for the committor the right panel. Though the plots do not extend to values of comparable with the largest values of E, [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 T = 30 and that, for this choice, the relative variance of the LSTD estimator significantly smaller than the relative variance of the MC estimator. The bounds in 66) and (7) are designed to capture the high accuracy of LSTD for relatively small values of r 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 7 is increased above T
Effect of the initial distribution. So far, in our experiments, we have chosen ja to be the uniform dis- tribution D. A natural alternative strategy is to harvest many short trajectories from single, much
Passage Time
Committar
max releive esymotrtic ver
bound
max reletive ssymototicc
1010
20*
10²
1.0
16a
10²
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 r. 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.
7

---

Mean First Passage Time
Committor
225.2
200
(relat ve MSFII 3
(rolst MSEII"
02
20
-00
11-20
(1-40
0.75
0.00
1.00
(1-1W0n-31
(1-300-11)
Figure 4: The relative asymptotic variance (solid lines) and the relative empirical MSE (circles) of the LSTD estimators of the mean first passage time and the committor, with j being the invariant distribution p conditioned within D. Note the scale is logarithmic. The relative empirical MSE are obtained with sample sizes M = 10n2. For n = 80 the TD estimator fails with high probability and the empirical error is undefined.
longer trajectory. Under ergodicity assumptions on P. these short trajectories are then approximately drawn from the invariant distribution of P. In Fig. f 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 in (9) conditioned within D. For 7 and n 20, 40, and 80, the maximum relative asymptotic variances of the LSTD estimators grow exponentially with n. With M = 10n², 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 LSTDD estimators with high probability, and the empirical error is undefine. These results should be contrasted with the much smaller errors shown in the middle panels of Figs. [ and corresponding to uniformly chosen initial conditions. We expect that the results in Fig. 4 would be somewhat different if, instead of initializing trajectories independently from the conditional invariant distribution, we had harvested correlated initial conditions from a single ergodic trajectory. Nonetheless, the results indicate that the choice of μ can have significant impact the performance of LSTD for prediction of rare events.
4 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 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 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.
On the other
To ensure that unique ū will exist for large enough M, we make the following minorization assumption on μ..
Assumption 1 (Lower bound on μ)) For some constant o 0, independent of n, and all E D. ((i)
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, its minimum is exponentially small in
As mentioned in Section 1.2 the perturbations, ŠT - ST, 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 Š" is the empirical frequency of a specific transition. As a result, the variance of St (i) is proportional to (i. perturbations by characterizing the entries themselves. Different entries of S* 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, upgrade [n]] to unweighted directed graph G by including edges
5t (i.))) S St (i. and we can characterize the
8

---

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.
only along transitions with significant probability. Our additional assumptions will be stated in terms of properties of this "minorizing graph."
Specifically, we introduce a directed edge from state i E G to another state j E if (T.)) 2 c, where c is a positive constant independent of the number of states nl. Assumption (Connected minorizing graph). For some constant c 0 independent of n, any two states D and [n] are connected by path in G.
When is irreducible, as assumed in Theorem T and n fixed, we can always find a > so emphasizes the
that any E D and j E [ni] are connected by a path in G' for r 1. A 2 eerppptiiinmemmpiiiiiieeeeee independence of n, asserting that the transition probabilities above the threshold can, on their own, preserve the connectivity of the graph while increases. Recall that the Markov chain studied in Section satifies P(i, 1) 2 e/2(1++e) implying that Assumption is satisfied with the choice =1/(((1 + e)).
Let j(i.j) be the length of the shortest path from state state j in G. When the graph is undirected, iss 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-Gare Gaussian" transition probability tails). For some constants B > 0 and C, independent of n. for all + j. and S (i.j) Ce- (1d)).
Assumption 3 stipulates that transition probabilities decay fast enough for distant states in G. For the Markov chain studied in Section 3 when r = 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 Section 3 the global landscape of the transitions exhibits challenging traits such as multi- molti-modality.
Illustration. The left panel of Fig. 5 depicts a general (symmetric) Markov chain on graph. Darker edges indicate higher transition probabilities. The transition probabilities are chosen to decay with Euclidean distance the plane, consistent with, for example, a Gaussian transition kernel in the plane. The minorizing graph on the right retuins 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.
considered the effect of the choice of on relative asymptotic variance. In that example, a larger choice initially increased the probability of nearest neighbor transitions and would allow for larger choice of As T increases further however, the probabilities of distant transitions would become larger, potentially decreasing the maximum allowed choice of and possibly requiring smaller choice of and/or larger choice of C in Assumption 3 The quantitative interplay among c, 3 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.
In Section 3]
As the experiments in Section S clearly demonstrate, these assumptions allow both the typical escape time and the relative variance of the MC estimator to scale exponentially with The failure of MC in these scenarios does not contradict this paper's 's theoretical results because the MC estimator does not satisfy Assumption 2 Indeed, the MC estimator corresponds to oc, for which S" (i.j) can only be non-zero if E D.
With these assumptions, we can now state our upper bound for the rare event setting, whose proof very simple but informative. The key idea is that, under these assumptions, Q"(h: E) in the denominator is indeed much larger than the transition probabilities (*,, E) in the numerator.

---

Theorem 2. Under Assumptions and 3
we have the following asymptotic variance bound:
of 22
C
(l
Te
11
(12)
When R(i) for all i D,
o
C
(log e)
n
(13)
Proof of Theorem Because Q" (k: E) is the sum of the probabilities of all paths connecting states and state that do not return to h and do not exit D (except through é), Assumption implies that
(kk
Plugging this bound and the ones in Assumptions 1 and into (6)
we find that
e [=d[k.]](2loocc2044...
NED.Eelm) Egk
Optimizing the summand over d(k: 2) gives the bound in 12 The bound in (13 follows from the same argument using 7 instead (6).
Remarkably, the total amount data (measured in observed transitions of X2) required achieve fixed relative accuracy has reduced from as bad as exponential in for the MC estimator to worse than n² 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 data set observed Markov chain transitions that dramatically smaller than would be required by the Monte Carlo estimator. In particular, the LSTD estimator 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 large error when the typical timescale of the rare event is large.
Generalization of our basic conclusions beyond the tabular setting is 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 A version of those bounds that applies to Markov processes in continuous spaces would have many interesting consequences, including in analysis 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 variant of classical Richardson iteration in which the residual of (2) 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 large. This issue has been explored in [Strahan et al.) (2023b), where the authors suggest batch version of subspace iteration for online policy evaluation and demonstrate improved convergence. The data requirements that scheme should studied theoretically.
10

---

Acknowledgements
This work was supported by the National Science Foundation through award thank Aaron R. Dinner, John Strahan, and Robert J. Webber for their help exploring early versions of our results. We are grateful to Joan Bruna, Yaqi Duan, Yuehaw Khoo, Yiping Lu, Christopher Musco, and Jonathan Niles-Weed for helpful discussions. This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise.
We
References
Adam Antoszewski, Chatipat Lorpaiboon, John Strahan, and Aaron R. Dinner. Kinetics of phenol escape from the insulin r6 hexamer. The Journal of Physical Chemistry B, 125(4)): 2021. doi: 10. 1021/acs.jpcbb Ic06544. WRI.https:// //attps://do... http://doooorgg1..111/1 10200002///c// jptp://p.....ppp.p...pppppp 1c06544
PMID: 34648712.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Armand Prieditis and Stuart Russell, editors, Machine Learning Proceedings 1995, pages 30-37. Morgan Kaufmann, San Francisco (CA), 1995, ISBN 978- 978-1-55860-377-6 doi: https://doi.org
www.://rrttertttteeeeeeeeeeeeeee cttp/science.
orticcle/p1//9971556666777
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings the 31st Conference On Learning Theory, volume 75 of Pro- ceedings of Machine Learning Research, pages 1691 1691-1692. PMLR, 06-09 Jul 2018. URL wttpppessss////pppppppppppppppat
https://prroceedings mlr www.pprsssssee v75 http://///haaaaaaaaaaaa www.bbaaanaaiiaaaa 1aaamdaar188.... html
Steven Bradtke and Andrew G. Barto. Linear least-squares algorithms for temporal difference learn- ing, Machine Learning. 22(1):33-57, Jan 1996. ISSN 1573-0565, doi: 10.1023/A: 10.102//:1111006110000 1018056104778.
URL https: org/ 10. 1023/1 A 1018056104778
James Antonio Bucklew. Introduction to Rare Event Simulation. Springer Series in Statistics. Springer New York, New York, New York, 1 edition, 2004. ISBN 978-0-387-20078-1 doi:
00.100079988-14475--4777-
Qi Cai, Zhuoran Yang. Jason D Lee, and Zhaoran Wang. Neural lemporal-difference learning con- verges to global optima. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bus E. Fox, and R. Garnett, editors. Advances Neural Information Processing Systems, volume 32, Cur- ran Associates, Inc.. 2019, URL https: newrriiidiiiinnnniiipiso.... www..ns..ccppppe.r.... http/ppperffflls/eeeeee 200psffiieeaaaaee2fff66662222222
pddf
David Cheikhi and Daniel Russo. On the statistical benefits of temporal difference learning. In Proceedings of the 40th International Conference on Machine Learning, ICML'23, JMLR.org. 2023.
Pierre Collett, Servet Martinez, and Jamie San Martin. Quasi-Stutionary Distributions. Probability and its Applications. Springer Berlin Heidelberg, October 2012. ISBN 777-3-644-33310--5 URL https: httap:://link.aat spriinkksspinger...... com wtt..ccw.coooeeceeee 10.
Gal Dalal, Balazs Szorenyi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for td(O)
with function approximation. In Proceedings of the Thioty-Second AAAI Conference Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI Press, 2018. ISBN 978-1-57735-800-5
18/EA// 18//AAAAAA/AAAATTT 18.
Christoph Dann, Gerhard Neumann, and Jan Peters. Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research, 15(24):809-33 883, 2014. URL
http:///jmrr www.ooog/eeeeeeeeooooooo httg:/apprssvvvv.. httl/////////nnn/// dann14a. html
Peter Dayan and Terrence Sejnowski. Td(A) converges with probability 1. Machine Learning, 14: 295-301, 1994. URL https://api http:/ppp..mmmaiiiiccccccclaaarl htt.://aa....rgg/ooooooiiD00:::

---

James W. Demmel. Applied Numerical Linear Algebra. Society for Industrial and Applied Mathe- matics, 1997. doi: 10.1137/197816111774448 Uttptts: siam. htrg/do//abs/. 1137/1.9781611977
Justin Finkel, Robert J Webber, Edwin P Gerber, Dorian S Abbot, and Jonathan Weare. Learning forecasts rare stratospheric transitions from short simulations. Monthly Weather Review, 149 (11):3647-3669, 2021.
Justin Finkel, Edwin P Gerber, Dorian S Abbot, and Jonathan Weare. Revealing the statistics of extreme events hidden in short weather forecast data. AGU Advances, 4(2x=2023AV008811 2023a.
Justin Finkel, Robert J Webber, Edwin P Gerber. Dorian S Abbot, and Jonathan Weare. Data-driven transition path analysis yields statistical understanding of sudden stratospheric warming events in an idcalized model. Journal of the Atmospheric Sciences, 80(2):519-534 2023b.
Steffen Grunewalder, Sepp Hochreiter, and Klaus Obermayer. Optimality of Istd and its relation to In 2007 International Joini Conference on Neural Networkx, pages 338-343, 2007. doi: 10.1 10.1109///CN 200. 4337099..
Steffen Grünewälder and Klaus Obermayer. The optimal unbiased value estimator and its relation to 1std, td and mc. Machine Learning, 83, 08 2009. doi: 10. 10007//19994-11-5220000
Spencer C. Guo, Rong Shen, Benoît Roux, and Aaron R. Dinner. Dynamics of activation in the voltage- sensing domain ciona intestinalis phosphatase ci-vsp. Nature Communicationns (15):1408, 2024. doi:
httpstss: org/ 0036//41447-0024455554
Brooke E. Husic and Vijay S. Pande. Markov state models: From art to science. Journal of the American Chemical Sociery, 140(7):2386 2396, 2018, doi: 10.1021/jacs77112111. URL https://doi
httg///ii.org/////// 10. 1021/jacs. /b1t//9991s..11191 PMID: 29323881.
Tommi Jaakkola, Michael Jordan, and Satinder Singh. Convergence of stochastic iter- ative dynamic programming algorithms. In J. Cowan, G. Tesauro, and J. Alspec- tor, editors, Advances in Neural Information Processing Systems, volume 6. Morgan- Kaufmmann 1993. URL httpps: http://ooccediin...eerirpppppppp meeurips.cc/ppper.ee...... hcccpaper.fillspppee///ee Fll2/507728saaaa3333000556666622
Valérian Jacques-Dumas, René M. van Westen, Freddy Bouchet, and Henk A. Dijkstra. Data- driven methods to estimate the committor function in conceptual ocean models. Nonlinear Processes in Geophysics, 30(2): 216, 2023. doi: 1451994npg-30-1999 195-2323. URL https
Timothy Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning, 2019.
Dario Lucente, Joran Rolland, Corentin Herbert, and Freddy Bouchet. Coupling rare event algorithms with data-based learned committor functions using the analogue markov chain, 2021. URL
https://arxiv wwwpsrxwwv..orra/ee http//bb//211..... 05050
Peter J. Schmid. Dynamic mode decomposition and its variants. Annual Review of Fluid Mechanics, 54(Volume 54, 2022):225-254, 2022. ISSN 1545-4479. doi: https://doi.c org/ -itp:aannneey--iuii-000011111111 journals/ 10.
URL http:: annualreviews. wwwpeewwwwwws./eoeeeeeeeeeeeeeee content// www.dffuuuddd11oa 11180122--01855
R. Srikant and Lei Ying- Finite-time error bounds for linear stochastic approximation and td learning.
In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2803-2830. PMLR, 25-28 Jun 2019. htRps:/:::/// htt.httss//prrcceddnngee//// mlr. wwwpprrssvvvi v99/ sr kant 1 html
John Strahan, Adam Antoszewski, Chatipat Lorpaiboon, Bodhi P. Vani, Jonathan Weare, and Aaron R.
Dinner. Long-time-scale predictions from short-trajectory data: A benchmark analysis of the trp-cage miniprotein. Journal of Chemical Theory and Computation, 17(5) 2963, May 2021. ISSN 1549-9618. doi: 10. 10.1//acs.cttc..co0033.. URL Oc00933
1021/0100.1///0 jctt jetc
12

---

John Strahan, Justin Finkel, Aaron R. Dinner, and Jonathan Weare. Predicting rare events using neural networks and trajttrry data. Journal of Computational Physies, 488: 112152, 2023a. ISSN 0021-9991. doi:
1122111122. URL
John Strahan, Spencer C. Guo, Chatipat Lorpaiboon, Aaron R. Dinner, and Jonathan Weare. Inexact iterative numerical linear algebra for neural network-baset spectral estimation and rare-event prediction. The Journal of Chemical Physics, ( 07 2023b. ISSN 0021-9606. doi:
10.1063/5.0151399, URL https://doi..i.i. org/ 10.
Richard S. Sutton. Learning predict by the methods of temporal differences. Machine Learning, (1):9444, Aug 1988. ISSN 1573-0565. doi: 10. 1007/BFF00 1100001550099 15009. URL URLhtss:s://do/ org/10 10
1007/BF001150
Richard Sutton and Andrew G. Barto. Reinforcement Learning: Introduction. The MIT Press, Cambridge, Massachusetts, second edition edition, 2018. ISBN 978-0-262-039944
Erik Thiede, Brian Van Koten, and Jonathan Weare. Sharp entrywise perturbation bounds for markov chains. SIAM Journal on Matrix Analysis and Applications, 36(3):917-941, 2015, doi: 10.1137/140987900. https:////
Erik H. Thiede, Dimitrios Giannakis, Aaron R. Dinner, and Jonathan Weare. Galerkin approximation of dynamical quantities using trajectory data. The Journal of Chemical Physics, 150(21)244411, June 2019. ISSN 0021-9606, 1089-7690. doi: 10. 10.1063/1.5063730
John N. Tsitsiklis and Benjamin Van Roy. An analysis of temporal-differencce learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674-690, 1997. doi: 10.1109/9. 580874.
13

---

A Proof of Lemmall I
Proof. Irreducibiliy and aperiodicity of SD implies that v/ is the unique left eigenvector Sp with
largest eigenvalue, Amus- Using the fact that the u(i) [T solves with R(i) 1 for i D E,, T T|. Therefore
and R(i) = 0 for & D, a direct calculation yields Eg [T] (1 max)
Ep [T]
[
[1(I - -(1- )
E, [T AT
and
E [
K² = =1 (1(-sp)-1111 Sbll
11 1b
B Properties of the Markov chain studied in Section
Proof of lower bound of ||T - Spll2- Let Sp be the restriction of Sp to row and column indices in D, i.e. the (n 2) (n 2) submatrix in the middle of Sp. Sp is substochastic matrix that satisfies detailed balance with respect to p in ( for those entries in D. Therefore, ŠD is similar to real symmetric matrix, and all eigenvalues of Sp are real. Let mmia be the smallest eigenvalue of Sp. We have
| Spl22 2 Amin-
We will derive an upper bound of Amin show that /|/ Splla bounded away from 0.
Define an (n - 2) (n - 2) diagonal matrix Dp as (i, i) - p(i + 1). Note the index adjustment is due to the size difference of Dp and p, and similar adjustment will persist in this proof. By the detailed balance property $p(i,j)p(t 1) Sp ij + 1) for i, I,..., 2, the matrix A D3 Dp is symmetric matrix, and it has the same eigenvalues as Sp.
Now we will give an upper bound of Amins the smallest eigenvalue of A. By Rayleigh quotient characterization of Amin, any length n 2 nonzero vector satisfies Amin I AnAr Specifically, we choose v as
i(n 2) ) i= 1,2, n 2. n
(11 n sin
The motivation is that in the limit - oc, A will be related to (weighted) finite difference matrix for the Laplace operator one dimension, so we would like to use u which is unit eigenvector corresponding to the smallest eigenvalue of the Laplace operator.
Our remaining work is to calculate v' Au and upper bound it. A is tridiagonal matrix with A(i,
A(i, 1/ [2 (v
piti
Pi+2
A(i 1, 1/ 2
pis1
PE12
Pill
PEL
P4
By direct calculation, with n-I we have
J
Au
2 n-2
Pi+2
2(p p.) )
Pi
1 cos(2ia))
n
2(p++1 1 P142)
i=1
n-2 1
2
cos cos((2i + 1)a)]
71
4
Del2
PELl
V
n-2
2
cos + cos((2i - 1)a)].
4
Pit1
Pi-1
According 9. e <
IP()/p(ii < for I/ -i 1. We also have the incquality / = /
Ri 2 2.
Applying these bounds and separately summing terms of cosines with positive and negative signs,
14

---

have an upper bound
(n 1)
Amin <v'
--
2
1-
1
1
cos(2ia)
l+e)
n-
1+c
11 2
+
Σ
cos (2a))
+
n
36n
17
COS a
(n 2)
2(n - 1)
Ve
Jn -1
1
cos( -)a)
n1
2/ee
1
+ n - 12
cos( - 11)a)= +
cos( 1)a)
5m-1
Σ
cos cos((2i 1)a).
4(n - 1)
i=1m
Using exact formulas of sum of cosines, we have
Amiin S TT Au - n1 2
1
sin(oaia)
1
n-1 1
1 1 sin cos(abin)
1
1 1+6
1
(sin(aa22)
sin(aaan)
(1
1 1 1+e-1)
cos((bzz)) + sin
cos cos(ab)))
sin
COS a
N1 2
2(n - 1)
Ve
1
sin(caaa) cos(a)an)
n 22
sin
1
[sin(aasa)
sin((a06)
sin cos(absn) +
cos (os(aben) )
n -12
sin a
+
1
Σ
cos((2i- - 1)a),
4(n 1)
1m
with Oin
3(n-1)
n1-1
1. bin
3(n 1)
Q2n = [1=1 b2n n-1 + [n-1]
1
4
1
a3n 71
3(n-1)
1
ban = n 2+
3(n
4
04n = | - [ + 1, byn = 3n-1
[x+1] - 1, Aan
n+1
1, b.. = n+1
+
A6n = n -n 3n-11 b6n = n - 3 3n + oo for all other i's. Similarly, ab;, have
Note that 00in. 0.04n
and 0djn "
corresponding limits. Also, (n - 1) sin a - т. Based on these limits, as n - xx, the right hand side of the inequality above also approaches limit. Specifically in the limit,
1
1 1
lim sup Amin S (1 1te n-
2 + (
2
Ite Ite- 2
Therefore, lim inf ||/ - Sp 2 2 1 lim sup Amin > 0.36. This shows that for large
||/ Spll2 is bounded away from
Proof of 10 We can find explicit formula for u by solving the linear system
p(i 1)
p(i +
2(p(i) + p(i - 1)) (u(i) ((i))u((-1)) = 2(p(i) p(i + (u(i+t)- i= 2,3,..... n-
(14)
15

---

with u(1) = u(n)= = O. This yields
p(t) p(i)+p(i+11
p(t) + ) p(i)p(i+1)
[
pli) + p(i 1(
$p(s))
u(k)) 2 2
p(i)p(i+1)
p(t)pi+
F-2
p(0) +(0+++++1)) p(Op(i+ +)
p(t) +
Σ p())
(15)
p(1)p(++1)
By the symmetry of p.
11 n+
p(1) + p(i+1))
=2
2
p())p(++1 1)
p(i) + 1(i+1)
p(i) 100+p(i+))
Emoo))
p(1)p(i+1)
p(i)pi 1)
1=2
+
p(t) + p(
Ep(e)
p(i)p(i+1)
p(0)p(i+11 P=
p(1) + p(i++1)
2
p())p(i+1)
a41 Σple))
p(1)
p()+p(iit))
p(t) + p(i +1)
Σm() +
p())p(++1)
p(i)p(++ +1)
1=2
t=2
+()+p(i+1)
p(i) + +(i
Σ p(e)
p()p(i+11)
p(i)p(++1)
2
n+1
p(t + p(i++))
p(i) + p(i p(i+1) p(i)p(i+1)
2
Σ p(t) 1=2
p())p(i+1)
2
p(i) + p((++))) p(0p(i+11
p(1)+ p(1)+p(i+11
p())p(++1)
p(i) + p(i p()((1 +1)
(16)
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.
n 2
2
max
1 p(1)
4 exp
13exp(
4m
3
4
exp
3(nn= - 1)
8TT
(17)
More carefully, for any small and for these terms, p(1) < 3 exp( m-1 (-2 =)). Therefore,
E >> 0, there are (n), cos( 4 terms that are smaller than 1 + 6,
n-1
n +1
2 nexp (" nn- 1 (2 - E)
u
(18)
2
4T
16

---

Proof of 11 This time u(t) solves
p(i - 1)
p(i + 1)
((p(i) + p(i - 1)) (u(i) uli 1))
2(p(i) p(i 1)) (u(i+1)) + -)-())) i= ........
(19)
with u(1) = 0, u(n)= 1. We find that
P(1) + p(2)
u(2)
(20)
12
p(i + p(++1j
i=1
loose bound is
(2) - p(1] ((2)
exp (- 1=1
+
exp
R-1
8i
S
exp
n1
(21)
max; p({)
exp
n-1
8T
4m
More carefully, for any small
> 0, there are O(n), cos
(T((-11))
terms that are smaller than
n-1
I resulting in the bound
exp
(n -
2
exp
(3 - E)
(22)
exx
(1 8)
8
C Proofs of main results
Proof of (5) in Theorem 7. Each entry of 5t s a ratio of two random variables, as
1 (*K (k, M Σ j=1 1 (a) (xt) (1(9)()) - -k,,))
(23)
Ar N7 Σ (xz)
We will prove all entries of S" for all < S satisfy central limit theorem by central limit theorem for the (normalized) numerators, and then apply Slutsky's ' theorem to include the denominators. By argument similar to the one used to establish Lemma I in Thiede al. (2015). u is a differentiable function of entries of 5*. The delta method, therefore, transforms a central limit theorem for these entries into central limit theorem for u.
Let M denote a matrix containing only the (normalized) numerators of Š' St. that is, M E) = + ΣN (1x (X6) (1ee) (X) (X(TT)) St (k. Let 1:r represent long vector formed by flatten- ing out each matrix M with 1 < t S 7 in row major order and gluing up in time order. Then, since trajectories are independent, M:r l:r satisfies a central limit theorem as
VM 2, N(O,E
(24)
For convenience, let 2M k1, (1), (12, k2, (2) denote the entry of Eii that records the covariance "M
Cov [1(k]
5th (ks, ()) . ((aa)(X)) (1{e)) (XL - 5t2 b2))
(25)
Since [(x)(X)) (Xo) for different ie can not nonzero at the same time, we immediately obtain
Sir ((t1, k1, 41), (t2, 62, (2) 0. for k + l2 and any é1, f1, L1, l2.
(26)
Now we deal with the denominators. Let f be the vector containing all the (normalized) denominators, that is, (ak) = 1 Mg. Then, again because of independence of trajectories, we have a weak law of large numbers as
M
P i
p.
(27)
17

---

where we recall that j is the initial distribution supported on D, and E, means convergence in probability. Combining 26 and 27 by Slutsky's theorem, we obtain central limit theorem for $ VM (il: s 2, NO,,
(28)
where Sir and Shr are vectors flattened out from S and S for S S 7 with the same order as in M l:r and
E ((11, k1, (1), (t2, k2) p(k))a((2))
((1, (12, N2, E2)).
(29)
According to
25 and (26
lsr ((t1, ki, (1), (12, k2, (2)) for K1 # 22
E ((t1, (,), (t2, k2 Ez)
(30)
Ek [(1çe)) (XLATT Sth (kI, Ei) (1(ea) (Xt2nT) St2 (k2, E2))
((k)
To transform the central limit theorem 28 to a central limit theorem of ū(i), we point out that u(i) is differentiable function of entries of S and now we are going calculate these derivatives. Entries in outside of D are fixed under any perturbation in St. To write down an equation satisfied by all entries of u, we rearrange into
T-1 (1- St + - (S Sp) t-
(31)
where (ix(i) LI R(i) for [n]. RD is vector whose nonzero entries are those fixed boundary values u. Because St is a stochastic matrix, we consider it to be determined by off diagonal entries as
=I= Σ
S',,, ((eke exeR).
(32)
KEEKED
This implies that
SD I
Σ (e(k,))(ezeT egeh)
Σ
S* S'kk Σ EeeT.
(33)
RED.EDDA
RED
RED
For specific pair (ks,) with k e D and l & k. we define (t(s) = St + +elenet - -exe)). Then we define
a () (5") = ass((k,)) (k, (S").
Ou
Oun
Oun (k,
(8t)
(S((E)))
de
Differentiating (1] with respect and taking care of (33). we find the derivative with respect to S* (k, E) for different k, t, The formulas are different for different t. For = T, k. l E D, we have
Ou (I (I-SD) (k)
(eLe) ege 0.
Therefore,
Ou
(T (T- (u(E) u(k))
(34)
OST E)
Instead, for l: E D2E D9, taking derivatives leads to
Ou
(I (I-S)) (S.(kk)) ele.u efef RD
du as in 34 after rearranging using the fact that RD (?) = which gives the same formula for (s-(k.)) u(() for é D
18

---

Fort < T, k E D and & [n], taking derivatives in 31 gives
du
= = -I
-h) ex (Ro(1) - Rb(k)).
(35)
as (k, E)
Now, we can use the delta method transform 28 a central limit theorem for ū(i) for any i D.
VM (ū(1) u(i)) 2x N(
(36)
with
iu(i) eu(i) 1: (tt( (1, k2)
of
Σ
a (ki, 1 0 (k2, E2)
k1 D.ED, l26ml ki kighf,, N22222
f1.2==1
Σ KED
(e. (c] -1-1-)) Ex
Σ (RD(1) RD(k))
-
u(k)
(E RiPM
27
+ (u(e) u(k))( -5 -
Σ
(cT - (1-5 Tex) E
Σ RD(()
Σ -
RED 1kk)
(E(m)
1=1
+ +u())(1 - S*,(,, 0)) 27
27
Σ
(e] (011-55)- -5)) Ex
Σ Rx((T) + w(Xxar) - (u(k) Roo(k))
RED l1kk)
Σ RD(XeT) + u(Xxar) (aax))u((A)) u(k)) )
Σ RED u(k)
(c] -bx)) 2E
Ex
(37)
The second equality is obtained by plugging in 335 that
34
and 30
The third equality uses the fact
Σ 1x(XAT) = Σ (k, 1, for any k D,LST.
RE(M]
RE[m)
The fourth equality uses the Bellman equation
Now introduce the key lemma for Theorem The lemma characterizes the continuity of the operator E, Σn= (X,) in terms of the initial state f. Note that dot product of this operator with the corresponding reward R(j) generates the value function u(E).
We define additional hitting times counting from = 0. That is, πg = min(t 2 0: X₁ = k}. This differs from 7І because Ti includes = 0. Similarly, we define 17 and more generally T' and 7 for any subset A C [n] the counterparts of 77 T'A and TT but counted from 0. But notice that we have defined T and 7" to be counted from f = 0. In all hitting time definitions, when the set over which the minimum taken is empty, the hitting time is defined be +00.
Lemma 2. For i D, L E [m)) & + E.
I Σ
T Σ 1=0
E,
Σt (x))
E,
Σ 1=0
(YT)
E,
(X,)
Ex
(x.)
<
(38)
(r(k,))
19

---

Proof of Lemma 2 The proof will proceed by representing all quantities by probabilities, and then with the help of complementary Markov chain, we can bound the difference of involved probabilities. We start with two basic identities that hold for any i, k E D.
P
Fg T
E
Σ 1
1 (ay (X7)
=
(39)
Ps [T TF
and
T
P T, T
Eg
1 [o (Xt)
(40)
Pj [T' < T3]
f=0
Note that when j D2, P, [T S 7,]
With
(39h and (40) the left hand side of 38
becomes
P; 7 T
P T 1
T
P
T ST
(41)
PA T < <T
Pj
IT
To make probabilities related to X, in 441 become probabilities related to 7-step transitions, we consider another Markov chain Y that follows the transition probability matrix Sj = (S,)*, where Sj defined as
due k=j,ee [m]. S, (
[K(K)) E)
k [n]
(42)
Sj is the same as S except it is stopped once j is hit. Note that when E D.. Sy = S. Define hitting times T7 TT and " of y similarly as those of Y," If Y hits j before k. then T +00, and this exception is similarly defined for other hitting times. Note that T counts from t = 0 as does T. One key relation between Y,T and XAAT is that
i
S = Pe T STNSST ST
Pe
(43)
This relation is guaranteed by the fact that Y. will stay at if a coupled X hits j at any time within each length-r time interval.
Now consider the case where & E D.j * and j + l, and identify all of D \ {i} with a single additional index A. Note that whether j E D or j Dr.
Pe
<T Pe
T
(44)
Consider another Markov chain Ze E {e, k, A} that records transitions only when Y," transitions between one of these states. We will use Q denote the transition probabilities of Ze. For example,
Q(e,)) = Pt 12 = = Pe ( < min , .T.. r
and
Q(C,k) P. [21 k] Pe
[ min((T) TT3, r
In fact,
Pe TTJ < T and Pk (TT' < T
satisfy the linear system
Pe T < x Q(e,6)p, [T - k(G, TT T Q(G,)),
(45)
Ps
T < T PP (T7' < T + Q(k, p)P2
TT TT ((k,)))
It is convenient to work with the normalized transition probabilities
Q(e,-) and Q(k,.) Q(k:.)) E(e,))
((c,-)
Q(k k)
With this notation, solving (45) reveals the identities
((k,)) + (((.5))
Pe 117' <T
1 1 Q(e,k)Q(k e)
20

---

and
Pk TJ T Q(k (((E))((E))) Q(k,))
- ((e,k))((k
from which, after a little more algebra, we find that
AI(E,))(() ()Q(E,)) Q(e,
Pt Pe T < PP <
T
(46)
This is the key quantity that characterizes the difference between probabilities with initial states l and l. By bounding this, we can finally get relative variance bounds. We observe immediately that
{ ()) 1 k(k S TT < T ((e,)).
Now we relate these probabilities to Y,, We have that Pa [T7 < T% T Q(k, + ((k, so
Q(k. (Q(() + Q(k.1) Q(K,Q 2 ((,,)).
PAITT <TAAT
((k,6) + ((k,
This yields
Q(, 1- (e, k) (K, E)
Pk T < T
Q(k, A)
P TV AT
Bringing these inequalities back into 46). with
and 44
we have
Q(k: A)
Pe Tj
T
Pk ,
T
TJJ
max Q(G,)),
ke
Ps I. < TAA
Now notice that Px
[T'
TV
Q(K A)
P
T7
TV ATT Q(e, and therefore,
P
1 s T
P T T
P I STT
(47)
P
T <
Tx
Ps T < Th ATT
Plugging
back into
we find that
T
T
E,
(xT)
Es
(X,)
- EE
Σ
1 (x)
1=
P Pz
P
T < T
P T ST
(48)
P,
7
S T3
Ps
[T < ATATT
P T, Ps T < ATATT
By (40) and the definition of Q (ki, 8) in Theorem E D.j + k and / L.
this the stated bound in the case where
Now we deal with the exceptional cases. When f E D but = or j = the same conclusion holds with minor modifications of the intermediate steps. Specifically, take j = & (so that E D and
A = D9) as an example. Then Z: E (e, k, A} records transitions of y,7 among these three states.
With Q denoting its transition probabilities.
Pr P
< T
P&
7
< TT
= 1 1 Q(k,)) = 1 =
and Ps [7
T. A T Q(k 0). Ps
[T)
T = [kk, E). Therefore,
P 7, x T|
P k
π x T| S
Ps T, < T] ((K,)))) Ps T7 <TTAAATT
We also note that Px (T < T > Q(: A). Then the following steps are the same as (47 and 48 in the general case.
21

---

When E D. j E [n] and & A, Pt
Tj ST 0.
P. k T
Pt T3 S T
Pe
T3 ST
P: T < T
Pk T3 ST
Pk T < T3l
P, T TT
Px TT T
P, [T <Tj
Pi TΙ ST
P Pa
T7. < < ted
Applying (40) to the right hand side, this gives the bound
38
When L D and j = f, Pt
= 1. We again use Q to record transitions of Y, (= Y7)
among j, A. Then,
P T T
Pe T3 S T
PA
T ST
P.
Th TT Pk (T <Tp P T ST
Pk 7 < T
P3 T TT
P T S T
P, IT IT
T7 < < Do
The last inequality follows from the facts that
1
1
(kkrj)
Pk [T] ST
Ps TT <
1- Qk:, Q(k,))
Pk T7 < Th A bex(0))
We thus prove that the bound
38 holds for any indices i, k. E D, l E [n] and l: & l.
Now we are well prepared to prove 6 in Theorem [
Proof of (6) in Theorem 7 We will interpret two main terms in probabilistically. First, for i, D,
(T- ST) - ek = (Sb)' (1, E, Σ (x7)
(49)
As the expectation following eT (11-55) -te in (5) we note from the Bellman equation 22) that
T-1 Es RD(X + u(XxAT) - u(k)) = Var Σ
Ro((er)) + u u(Xxxx))
where the subscript & indicates conditioning on Xo = k. Since this is variance, we can decompose into conditional variance of each step by the law of total variance, as
Vark Σ RD(X)T))++++ + u((TAT) = Ex
Var
Σ
RD(X)NT) + u((xAA)) Xo = ki XIAT
Vark
E
Σ
RD + u((xNT)
Xo = ki NIAT
(50)
By the definition of u, E EE=
RD(X)NT) + u(XxxT) Xo k, X
u(XIAT), which
helps to simplify the second term. Meanwhile, the first term can be simplified
Ex
Var
RD(XuNT) u(XxNT) Xo XINT
Ex
Var
RD((NNT) u(XrNT)
Xo= k, XIAT
22

---

We can further condition it on X2^T and perform a similar decomposition as in (50). which can be done inductively for XtT up to As a result of this inductive conditioning, we obtain
Ex
RD(Xerr) u(XxNT) u(k)
t=
Ep Vir-
(N(X)NT))) +...+ Ep (Varxaur Xanr (u(XaaT))) + (Var x (u(X2AT))
Vara Carn(u(XInT))
(u(t) u(k))²
Σ 8" (k,
fE Eyek
1=1
(51)
For the inequality, we use the property of variance that
Eg Var Varxx (a- (
& Es (Ex (UX
= (u(eee)) - u()))²
Now, we further decompose the difference u uk) into components that we have already bounded using the fact that R is nonnegative throughout our paper.
in Lemma 2
116)(X) }
Σ 1 (0) (X.)R()
lu(e) u(k)] =
E
E&
jEIm]
1=0
1=0
(52)
Σ (x))
(x))
Eg
E
RG)).
jE(m]
Then according to Lemma
2 we can bound the variation in u between states as
E, EL (x) RG)
u(i) Q" (k. E)
E, Σ
((7)
(u(e) u(k)]
(T,
jEIm]
Combined with 49 and 51.. this yields
1 1 (k,
of S ui
p(k)
(k,
RED
As for Corollary the strengthening comes from an intermediate step in the proof of (6
Proof of Corollary 7 If R(i) for any i D (for example, when the committor function),
then
Eg
Ro(XLAT) + u(X - u(k))
Σ ((((t) ((k))) 1).
(53)
BEin
Compared with 51
that the same following steps will replace St C) in Theorem by
ST for Corollary
23

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA]-
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked use checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No] is perfectly acceptable to answer "[No] providee proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
.
Do not modify the questions and only use the provided macros for your answers.
1.
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We made such statements in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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 long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
24

---

Justification: We have mentioned that we only deals with the simple case that is LSTD of the tabular setting of a finite state space in Section I.I We have also mentioned that the bound is not good for large lag times in Section We discuss in Section 5 that we do not deal with the online setting which more commonly used in practice for data efficiency. Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on 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 provide closed captions for online lectures because it fails 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 fairess.
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 in 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.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide assumptions with each theoretical statement. The complete proof's are either in the main text or the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be 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 or not)?
Question:
Answer: [Yes]
25

---

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.
Justification: In Section 1.1
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken 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 a specific model and empirical evaluation, 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 (c.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all 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 to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which 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 have some path reproducing 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 faithfully reproduce the main experimental results, 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.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
gablic/guidess Sww.e/Summimsioooooooooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "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 //nips. http:///wwpp../eeeoeoo//////oata
for more details.
26

---

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 should state which ones are omitted from the script and why.
reproducible, they
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 is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
For experiments Section 3 the corresponding settings are stated there.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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 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, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars 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).
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 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 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 the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
27

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
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 hounds in Section rather than argue computational feasibility or efficiency. Therefore, think such information will be departure from the key contributions of this paper and 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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't 't make into the paper).
paper (e.g., preliminary or failed experiments that het.iiieceetccscccceelleeeeee
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We have been aware of the NeurlPS Code of Ethics and the research conforms with thtat.
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 deviation from the Code of Ethics.
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: The paper is on theoretical advantages temporal difference learning. We expect it to have long-term impact many different applications in machine learning, some which might have positive effects on society, some negative. However, since the work currently quite distant from concrete applications, it is difficult 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 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), 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
28

---

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.
If there are negative socictal 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
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)?
Question:
Answer: [NA]
Justification: There is no such models or data released in the paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not existing assets.
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 dataset.
The authors should state which version of the asset used and, if possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi 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-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
29

---

Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not 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 expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "bOrxv9itrn", "reviewer": "Reviewer_4mMw", "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.", "questions": "NA", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- An upper bound on the relative asymptotic variance is provided for LSTD\n\n- This paper considers the policy evaluation for rare event, which is new to the best of my knowledge", "weaknesses": "- There is no simulation results for rate event scenario\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review of the paper and supportive comments. \n\nFor a detailed response regarding our numerical experiments, please see our General Response.\n\nGiven space constraints, our goal in Section 1.2 was to *very* briefly summarize basic matrix perturbation and quasi-stationary limit results that motivate and position our contributions. Precise statements of our theoretical results are stated in Section 4 where the key assumptions for the rare event problem are introduced. But we appreciate that we can strike a better balance of precision and brevity in Section 1.2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nhVntZkHXb", "reviewer": "Reviewer_251G", "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.", "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.\"\n2. 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$?\n3. 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$?\n4. 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?\n4. $S$ is used in footnote 1, but defined later. Can the authors fix this?\n5. How have the authors addressed the bias-variance tradeoff in TD vs MC methods?\n6. As per the expressions given after line 87, are all states $i \\notin D$ stationary states?\n7. 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?\n8. What errors does the minorizing step in Section 4 introduce?", "limitations": "The authors mention the limitations in their work as points in different sections but do not provide a separate section only discussing these.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper is mostly clear and the problem selected is an interesting and relevant one.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the opportunity to respond to detailed questions. We respond to specific comments below. Space for our responses is limited, so please let us know if you have additional questions.\n\n**Weaknesses**: \n\nFor a detailed response regarding our numerical experiments, please see our General Response.\n\nRegarding practical applications of our results, we hope our paper will prompt a greater focus on rare events and their challenges within the reinforcement learning community as well as highlight the potential exponential benefits of TD over MC in those scenarios. As in our related work section, although TD has been a central idea in RL, quantitative characterizations of its benefits over MC have been lacking. Meanwhile, in extreme event prediction for scientific applications, machine learning procedures based on the MC estimator are common. By characterizing scenarios where TD excels, our paper can guide practitioners to make informed decisions about when to use TD and how to tune parameters such as the sample size and lag time according to the problem.\n\n**Questions**:\n\n1. The statement at line 49 is intended to convey that we consider both cases in which the escape time from $D$ is very large and cases in which only low probability escape paths accumulate significant values of $R$. Both are cases in which the MC estimator is very inefficient. We will state this more directly. Concrete examples of $D$ and $R$ corresponding to common rare event statistics are given in Sec. 3. In the mean first passage time estimation problem in Sec. 3, we do not distinguish between different escape paths. In the committor estimation problem we estimate the probability of escape at $n$ (and not at 1). These two problems illustrate the essential difficulties.\n2. Yes, throughout the paper $T$ is the stopping time defined after eq. (1). Please also see our answer to Question 7. \n3. Please also refer to our answer to Question 1. It is possible to have very large (small) values of $u$ without any rare event by simply choosing $R$ to be large (small). It is the variation in the accumulated reward over different possible trajectories that leads to large error for the MC estimator.\n4. In our setting the MC trajectories must extend all the way until time $T$ in order to construct the MC estimator (lines 59-60). With a discount factor of $\\gamma$, the value function can again be written as the expected accumulated reward up to a geometrically distributed time, $T$, with mean ($1/(1-\\gamma)$). An unbiased MC estimator would again require trajectories that extend to this time. In either setting, limiting the length of trajectories will introduce bias (even in the large $M$ limit) to the MC estimate.\n5. Thanks! We will address this.\n6. Since the bias of TD in our finite state setting decreases with $1/M$, for large $M$, the MSE of TD is dominated by its variance. The MC estimator is unbiased, so we characterize only its asymptotic variance. Since the bias of the TD estimator decreases as the lag time $\\tau$ increases (i.e. as TD approaches MC), one could consider the bias variance tradeoff as a function of $\\tau$ with finite $M$. This is an interesting question, but requires non-asymptotic bounds for bias and variance to address. The overlap of empirical relative MSE and asymptotic variance in the middle panels of Figs. 1 and 2, strongly suggests that the bias of TD is dominated by its variance in the rare event setting. \n7. The transition matrix of $X_t$ is $P$ (not $S$) and $X_t$ need not stop when it escapes $D$. However, $u$ only includes rewards accumulated up to escape. So, for the purpose of constructing any estimator of $u$, we can regard states outside of $D$ as stationary. This leads to the Bellman equation eq. (2) upon which the TD estimator is based.\n8. TD does require escape events in its data set. The data set used in Sec. 3 uses initial conditions drawn from the uniform distribution. Some trajectories started near states 1 or $n$ do escape before time $\\tau$. However, most trajectories in the TD data set need not escape, and those that do are of length no longer than $\\tau$. In MC every sample trajectory needs to escape and the trajectories can be of arbitrary length. Applying the MC estimator using only trajectories that escape within time $\\tau$, would produce very biased estimates (the estimate of the mean first passage time would always be less than $\\tau$). Understanding the performance advantages of TD over MC is a long standing challenge. While the TD estimator does exploit Markovianity, the key to TD’s dramatic performance advantage in the rare event setting (and in particular in the numerical experiments in Sec. 3) is that it uses estimates of many relatively large quantities (matrix entries referenced in Assumption 2) to estimate rare event statistics. Assumption 2 ensures that this is possible, as discussed more in our response to Question 9. We will provide this intuition more explicitly in Sec. 4.\n9. The minorization referred to in Assumption 2 is not an approximation. It stipulates that any two states can be connected by a sequence of transitions, each of which has, individually, significant probability, even if transitions between the two states are very rare. As our examples in Sec. 3 demonstrate, this assumption does not at all rule out rare events. Returning to our answer to Question 9, Assumption 2 ensures that the TD estimator implicitly expresses the rare event statistic of interest in terms of statistics (non-negligible transition probabilities) that can be estimated with small relative variance. Assumption 3 ensures that other “small” entries in the matrix do not spoil the accuracy of the estimator.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VStpaMIUsA", "reviewer": "Reviewer_piRP", "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$.\n\nThe 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.", "questions": "No questions at this point.", "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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Overall great paper. The setting is sharp and precisely captures the phenomenon to be studied. The paper relies on a key original insight that links locality of transitions and efficiency of TD estimators for rare event estimation.\n\nThe related work is clearly covered, and the paper convincingly distills the key insights from previous empirical and theoretical studies into a set of assumptions and their consequences in the setting of an asymptotic central limit theorem.\n\nThe setting is consistent with standard notions of Markov chain literature. The key ideas are nicely illustrated using examples and pictures. Presentation is sharp overall.\n\nThe clear understanding of why and when TD performs well allow practitioners to make an informed choice on when to use TD for sampling problems.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback and acknowledgement of our work’s contributions. While our specific contributions are statistical in nature, we feel they are very relevant to machine learning based prediction for rare events. For example, in the context of extreme event prediction for scientific applications, machine learning procedures based on the MC estimator are common. Our results help to explain the relative effectiveness of recent TD based rare event prediction schemes cited in the manuscript. We hope to build a bridge between the scientific community, which studies rare events, and the RL community, which seeks theoretical foundations for the benefits of TD. This interdisciplinary focus also motivated our decision to submit to NeurIPS rather than a statistics journal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for their time reviewing our work, and a number of thoughtful suggestions for how to improve the presentation of the paper. We have responded to all individual comments below, but please let us know if any other questions arise.

There is a shared point of discussion raised by reviewers about the numerical experiments, which we address here. We present numerical results in Sec. 3 before the mathematical formulation of rare events setting in Sec. 4. We apologize for any confusion arising from this arrangement. We intended to motivate the development in Sec. 4 using concrete examples. We will identify this connection more clearly at the beginning of Sec. 3. 

In fact, the examples in Sec. 3 satisfy the assumptions in Sec. 4, as commented after each assumption (lines 285-286 and 292-294). Also, our numerical results in Sec. 3 precisely exemplify the key theoretical findings in Sec. 4. In Figs. 1 and 2, the empirical relative MSEs of TD (circles) align with the theoretical relative asymptotic variance (lines), and support our prediction in Theorem 2 that asymptotic relative MSE will grow slowlier than $n^3$. The relative MSE of the MC estimator increases exponentially in $n$ in the right panels of Figs. 1 and 2  (note the different y-scales in the middle and right panels). While the assumptions in Sec. 4 cover more general cases, our numerical experiments in Sec. 3 concisely demonstrate the key ideas.

Meta-review: 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.
Decision: Accept (poster)