Managing Temporal Resolution in Continuous Value Estimation: A Fundamental Trade-off
Authors: Zichen Zhang
Johannes Kirschner
Junxi Zhang
Francesco Zanini
Alex Ayoub
Masood Dehghan
Dale Schuurmans
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Policy Evaluation
Temporal Discretization
Continuous Time
LQR
TL;DR: To formalize the impact of temporal discretization in RL, we analyze Monte-Carlo policy evaluation in finite and infinite-horizon LQR systems and identify a trade-off between approximation and statistical error.

Abstract: A default assumption in reinforcement learning (RL) and optimal control is that observations arrive at discrete time points on a fixed clock cycle. Yet, many applications involve continuous-time systems where the time discretization, in principle, can be managed. The impact of time discretization on RL methods has not been fully characterized in existing theory, but a more detailed analysis of its effect could reveal opportunities for improving data-efficiency. We address this gap by analyzing Monte-Carlo policy evaluation for LQR systems and uncover a fundamental trade-off between approximation and statistical error in value estimation. Importantly, these two errors behave differently to time discretization, leading to an optimal choice of temporal resolution for a given data budget. These findings show that managing the temporal resolution can provably improve policy evaluation efficiency in LQR systems with finite data. Empirically, we demonstrate the trade-off in numerical simulations of LQR instances and standard RL benchmarks for non-linear continuous control.

Managing Temporal Resolution in Continuous Value Estimation: A Fundamental Trade-off
Zichen Zhang", Johannes Kirschner, Junxi Zhang, Francesco Zanini, Alex Ayoub,
Masood Dehghan, Dale Schuurmans
University of Alberta
{zichen2, jun. aayoub,masood1,, masood1, daes) Qualberta ca
Abstract
A default assumption in reinforcement learning (RL) and optimal control is that observations arrive at discrete time points on a fixed clock cycle. Yet, many appli- cations involve continuous-time systems where the time discretization, in principle, can be managed. The impact of time discretization on RL methods has not been fully characterized in existing theory, but a more detailed analysis of its effect could reveal opportunities for improving data-cfficiency. We address this gap by analyzing Monte- Carlo policy evaluation for LQR systems and uncover funda- mental trade-off between approximation and statistical eтror in value estimation. Importantly, these two errors behave differently to time discretization, leading optimal choice of temporal resolution for given data budget. These findings show that managing the temporal resolution can provably improve policy evalua- tion efficiency in LQR systems with finite data. Empirically, we demonstrate the trade-off in numerical simulations of LQR instances and standard RL. benchmarks for non-linear continuous control.
Introduction
In many real-world applications of control and reinforcement learning, the underlying system evolves continuously in time [Eliasmith and Furlong, 2022]. For instance, physical system like a robot is naturally modelled as a stochastic dynamical system. Nonetheless, sensor measurements are typically captured discrete time intervals, which entails choosing the sampling frequency or measurement step-size. This step-size is usually treated as an immutable quantity based on prior measurement design, but it has significant impact on data efficiency [Burns al., 2023]. We will see that, from data-cost perspective, learning can be far more data efficient if it operates at a temporal resolution that is allowed to differ from a prior step-size choice.
In this work, we investigate episodic policy evaluation with a finite data budget to provide a key initial step to addressing broader research questions on the impact of temporal resolution in reinforcement learning. We show that data efficiency can be significantly improved by leveraging a precise understanding of the trade-off between approximation error and statistical estimation error in value estimation - two factors that react differently to the level of temporal discretization. Intuitively, employing finer temporal resolution leads to better approximation of the continuous- from discrete measurements; however, under a fixed data budget, denser data within each trajectory results in fewer trajectories, leading increased estimation variance due to system stochasticity. This implies that, for a given data cost, it can be beneficial to increase temporal spacing between recorded data points beyond pre-set measurement step-size. This holds true for any system with stochastic dynamics, even if the learner has access to exact (noiscless) state measurements.
system
All authors contributed equally
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The main contributions of this work are twofold. First, we conduct a theoretical analysis focusing on the canonical case of Monte- Carlo value estimation in a Langevin dynamical system (linear dynamies perturbed by a Wiener process) with quadratic instantaneous costs, which corresponds to policy evaluation in linear quadratic control (I.QR). To formalize the impact of time discretization on policy evaluation, we present analytical expressions for the mean-squared error that exactly characterize the trade-off with respect to the step-size parameter. From this trade-off, we derive the optimal step-size for given Langevin system and characterize its dependence on the data budget. Second, we carry out a numerical study that illustrates and confirms the trade-off in both linear and non-linear systems, including several MuJoCo control environments. The latter also highlights the practical impact of the choice of sampling frequency, which significantly affects the MSE, and we therefore provide recommendations to practitioners for properly choosing the step-size parameter.
1.1 Related Work
There is a sizable literature on reinforcement learning for continuous-time systems [e.g. Doya, 2000, Lee and Sutton, 2021, Lewis et al., 2012, Bahl al., 2020, Kim et al., 2021, Yildiz al., 202 I]. These previous works largely focus on deterministic dynamics without investigating trade-offs in temporal discretization. A smaller body of work considers learning continuous-time control under stochastic [Baird, 1994, Bradtke and Duff, 1994, Munos and Bourgine, 1997, Munos, 2006), or bounded [Lutter et al., 2021] perturbations, but their objective is to make standard learning methods more robust to small time scales [Tallec et al., 2019), or develop continuous-time algorithms that unify classical methods in discrete-tinee time [Jia and Zhou, 2022a.b], without explicitly addressing temporal discretization. However, we find that managing temporal resolution offers substantial improvements not captured by previous studies.
The LQR setting is a standard framework in control theory and it gives rise to a fundamental optimal control problem [Lindquist, 1990], which has proven be challenging scenario for reinforcement learning algorithms [Tu and Recht, 2019, Krauth et al., 2019]. The stochastic LQR considers linear systems driven by additive Gaussian noise with a quadratic cost, minimised using feedback controller. Although this is a well-understood scenario with a known optimal controller in closed form [Georgiou and I. Lindquist, 2013], the statistical properties of the long-term cost have only recently been investigated [Bijl et al., 2016]. Our research closely relates to the now extensive literature on reinforcement learning in LQR systems [c.g. Bradtke, 1992, Krauth et al., 2019, Tu and Recht, 2018, Dean et al., 2020, Tu and Recht, 2019, Dean et al., 2018, Fazel et al., 2018, Gu et al., 2016]. These works uniformly focus on the discrete time setting, although the benefits of managing spatial rather than temporal discretization have also been considered [Sinclair et al., 2019, Cao and Krishnamurthy, 2020]. Wang et al. [2020] studies continuous- time LQR, focusing on the exploration problem. Basei et al. [2022] provides a regret bound depending on sampling frequency, for a specific algorithm based on least-squares estimation. Their analysis considers approximation and estimation errors independently, without identifying trade-off.
There is compelling empirical evidence that managing temporal resolution can greatly improve learning performance [Lakshminarayanan et al., 2017, Sharma et al., 2017, Huang et al., 2019, Huang and Zhu, 2020, Dabney et al., 2021, Park et al., 2021], typically achieved through options [Sutton et al., 1999], a specific instance of which is action persistence, achieved by maintaining a fixed action over multiple time steps (also known as action repetition). Recently, these empirical findings have been supported by an initial theoretical analysis [Metelli et al., 2020], showing that temporal discretization plays a role in determining the effectivvness of fitted Q-iteration. Their analysis does not consider fully continuous systems, but rather remains anchored in base-level discretization. Furthermore, only provides worst-case upper bounds, without capturing detailed practical trade- offs. Lutter et al. [2022] discusses the practical trade-off on time discretization but do not provide theoretical support. Bayraktar and Kara [2023] analyzes a trade-off between sample complexity and approximation error, which however requires the state and action spaces of the diffuusio process to be discretized to yield an MDP. The two components in the trade-off are analyzed independently, unlike the unified statistical analysis provided in our work, and no exact characterization is presented.
2 Policy Evaluation in Continuous Linear Quadratic Systems
In the classical continuous-time linear quadratic regulator (LQR), a state variable X(t) E R evolves over time & 2 0 according to the following equation:
dx (x dt + (U) dt + dW
(I)
2

---

The dynamical model is fully specified by the matrices A E R B R and the diffusion coefficient σ. The control input (t) E R' is given by a fixed policy, and ((t) is a Wiener process. The state variable (1) is fully observed. For simplicity, we assume that the dynamics start at (0) 0' E [c.f. Abbasi-Yadkori and Szepesvári, 2011, Dean al., 2020].
RD
The quadratic cost J is defined for positive definite, symmetric matrices Q E Rax" and R E RPx,, system horizon 0 oo and discount factor 7 (0,
J, J I 7 [x(1) QX (1) uU)+(()))))) (1) RU (1) dt.
In the following, we consider the class of controllers given by static feedback of the state, i.e.: (tt) = (t) where K E Rox= is the static control matrix yielding the control input. It is well known that in infinite horizon setting, the optimal control belongs to this class. Given such an input, the LQR in Equation (1) can be further reduced to linear stochastic dynamical system described by a Langevin equation. Using the definitions := A + BK and Q == Q + K RK, we express both the state dynamics and the cost in more compact form:
dx (t) AX (t) dt + a dw (t)
J. J+ (('''(()) (x))((())))))))))
(t dt.
(3)
The expected cost w.r.t. the Wiener process is V. = E [Jz]- The policy plays a role in this work solety from its impact in the closed-loop dynamics A. Equation (3) is what we analyze the following. We explicitly distinguish the finite-hooizaze horizon setting where t = 00, 7 < 1 and the cost is Vo In order not ineur infinite costs in either scenario, a stable closed-loop matrix A should be assumed. Note that the existence of a stabilizing controller is guaranteed under the standard controllability assumptions in LQR [Fazel al., 2018, Abbasi- Yadkori et al., 2019, Dean et al., 2020]. Thus the closed-loop stability can be safely assumed.
setting where r < co, S. 1 and the cost is Vr, and the infinite-
Monte-Carlo Policy Evaluation Our main objective in policy evaluation estimate the expected cost from discrete-time observations. To this end, we choose uniform discretization of the interval [0, 7] with increment h, resulting in N T/hh time points t4 == kh for {0. 1...., .N.. Here, the estimation horizon T, such that T < oo and T < T, is chosen by the practitioner (for simplicity assume that T/h is an integer). With the N points sampled from one trajectory, a standard way to approximate the integral in Equation (3) is through the Riemann sum estimator
(h) Σ nhX (tx) QX Qtx)t..
To estimate V,, we average M independent trajectories with cost estimates Jy.... JM to obtain the Monte-Carlo estimator:
M M Σ
M N ΣΣ
VM (h)
(h) M
-
* (tx) QX (tx).
k=0
Our primary goal is to understand the mean-squared error of the Monte-Carlo estimator for a fixed system (specified by A, and Q), to inform an optimal choice of the step-size parameter h for predetermined data budget B = M -N
Note that one degree of freedom remains in choosing M and N. For simplicity. require that in the finite-hone horie-horizon setting, the estimation grid is chosen to cover the full episode [0, 7] which leads to the constraint T N h. We write the mean-squared error-surface as function of h and B:
MSET (h, B) E (VVr V
In the infinite horizon setting, i.e. co, the estimation horizon T is a free variable chosen by the
experimenter that determines the number of trajectories through M = N 7F.
B Bh The mean-squared
error for the infinite horizon setting is given as a function of h, B, and T:
MSE (h, B,T) = E ((( (h) - Voo
(6)
3

---

Characterizing the Mean-Squared Error (MSE)
In the following our aim is to characterize the MSE of the Monte-Carlo estimator as a function of the step-size h and data budget B (and estimation horizon T in the infinite horizon setting). Our results uncover a fundamental trade-off for choosing an optimal step-size that leads to a minimal MSE.
One-Dimensional Langevin Process To simplify the exposition while preserving the main ideas, will first present the results for the 1-dimensional case. The analysis for the vector exhibits the same quantitative behavior but is significantly more involved. To distinguish the 1-dimensional from the nd-dimensional setting described in Equation (3), we lower-case symbols. Let xr()) E TR. be the scalar state variable that evolves according to the following Langevin equation:
dz(t) = ax((t dt + du(t).
(7)
Here, E R is the drift coefficient and (t) is a Wiener process with scale parameter > 0. We assume that a S 0, i.e the system is stable (or marginally stable).
The realized sample path in episode i = I....,M M is x1(() (with starting state zz0) = 0) and t e [0, T]. The expected cost
V, = R [. 7'r(()) ad = -[" [/][[a]()]] de,
(8)
where r1( qa.( (t) is the quadratic cost function for fixed q 0. The Riemann that approximates the cost realized in episode E [M] becomes J((h) = - (kg) Given data from M episodes, the Monte-Carlo estimator is Vs (h) M E J.(h). Since the square of the cost parameter y² factors out of the mean-squared error, we set q 1 in what follows.
3.1 Finite-Horizon Setting
Recall that in the finite-horizon setting we set the system horizon and estimation horizon T to be same. This implies that the estimation grid covers the full episode, i.e. 4.N T т. Perhaps surprisingly, the mean-s error of the Riemann estimator for the Langevin system (7) can be computed in closed form. The result takes its simplest form in the lmite-horizon, undiscounted setting where y 1 and < co. This result is summarized in the following theorem.
Theorem 3.1 Finite-horizon. undiscounted MSE). In the finite fnite-horizon, undiscounted setting, the mean-squared error of the Monte-Carle estimator is
MSEr B) = (1,,,T, + T2(
where
B E,,,,T,)) 0² (-2ah + e2ah - 1)² (62aT - 1)²
16a (eZah - 1)²
E2 ''T I (c2aT - 1) (4e + 2aT + 1) (c2ah - 1) (62ah + 4020T + 1) T]
2a² (e2ah 1)2
While perhaps daunting at first sight, the result exactly characterizes the error surface as a function of the step-size h and the budget B for any given Langevin system. The proof involves computing the closed-form expressions for the second and fourth moments the random trajectories (t) and is provided in Appendices A and B.1.
In the case of marginal stability (a = 0), simpler form of the MSE emerges that is easier interpret. Taking the limit - 0 of the previous expression yields the following result (refer to the discussion and proof in Appendix B.I):
Corollary 3.2 (MSE for marginally stable system). Assume a marginally stable system, Then the mean-squared error of the Monie- Carlo estimator is
222
AT
1
4T2 2hT h22)
MSE (h, B)
122
3
hB
3B

---

The first part of the expression can be understood as Riemann sum approximation enror controlled by the h" term. The second part corresponds to the variance term that decreases with the number of episodes as M B%h The remaining terms are of lower order terms for small h and large B. For fixed data budget B, the step-size h can be chosen to balance these two terms:
T
1/3
hr (B) == arg min MSEr B) R T h>o
3B
where the approximation omits higher order terms in I/B. From this, we can compute the optimal
BA (3) 1/3 Ba/s, We remark that under the assumption B > 1, also obtain that M > 1, This is in agreement with the implicit requirement that / is big enough to consider at least one whole trajectory, i.e. h > T/B.
number of episodes M ~ T
Consequently, the mean-squared error for the optimal choice of h (up to lower order terms in 1/ B):
MSEr(h", B) = 3 (3/2) AT -2/3
In other words, the optimal error rate as function of the data budget is O(B-2/3) We can further obtain a similar form for h* for the general case where S 0.
Corollary 3.3 (Approximate MSE). The MSE
(h, B) c1 a, + c2(0,0,T)
+ +0 + h
hB
for h and B - Dc, with system--eeendent constants
c1 0) = 04 (e2aT 1)2
c2(o,a,T)= -0a -0 T (4aT - eaaT + 200 (8aT - 4) + 5)
16a2
Sat
Moreover, for any h > 0 and B > O.
h22²
02 MS, B) 4a,h² + hB
202
hB
with c = ca 0, T) and 02 = (a, a, T) and the inequalities holds true up to a finite, lower-order polynomial expressions eth B poly(h, a, T),, given in Appendix B.2.
For the proof please see Appendix B.2, From the corollary, we can derive an optimal step-size, up to lower order terms in 1/B:
I²(B) (- [ 4o20 (8aT 4)+
1/3
B B-1/3
(10)
a"(c"ov-
Note that the same (B) also minimizes the upper bound the MSE up to a constant factor. The scaling (S" ( B) S O(B-0:(2))))) cannot be improved given the lower bound on the MSE. The derivation is provided in Appendix B.3 where we also include more precise expression of h².
Discounted Cost Adding discounting (r < 1) in the finite-horizon setting does not fundamentally change the results; however, it makes the derivation more involved (Appendix B.4).
Vector Case Addressing the general case (n- ne-dimensional Langevin systems with > 1) for stable matrix A requires forgoing the exuct form of the MSE. We derive tight bounds on the MSE, both of which are convex functions h, thereby narrowing down its behaviour with respect to the step size. The results are presented in Appendix C.3. Although the convex behaviour is proven only for Langevin systems, our experimental results in Section 4 exhibit a similar trade-off for general nonlinear stochastic systems.
Under the additional assumption that the matrix A is also diagonalisable, we are again able exactly characterise the MSE with closed-form computations. Diagonalisability is a mild assumption since it can be achieved under a controllable system. Indeed, controllability allows for the free adjustment of the eigenvalues of the closed-loop matrix A through the choice of the controller K. The eigenvalues can effectively be chosen to be distinct from each other to ensure a diagonalisable A. While the explicit form of the MSE is computable, its lengthy formula is not easily interpretable and is thus deferred to Appendix C. The following theorem summarizes the result as Taylor expansion for small h and large B.
5

---

discounted setting, the Theorem 3.4 (Mean-un squared error vector case). Assume A is diagonalisable, with eigenvalues A = (Ai,..,, An). The mean-squae squared error of the Monte-Care estimator in the fmite-horizon, undiscounted setting, is
MSET (h, = Ei (h, T,A)+ E2 AA)
where
B E (,A) = CC o T + 0(11)
E2 (h, =(22+C2
T
(1/BB)
B
hB
The proof, including the exact derivation of the constants C₁ C1 (A), Oz. C2 (A), can be found in Appendix C.I. Note that the terms composing the MSE closely resemble those obtained in the scalar analysis. In fact, when comparing them with the expressions in Equation (22) and Equation (23) (in Appendix B.3), the expression has the same order for h, B and T. The only difference is that in the vector case, cumbersome eigenvalue-dependen constants are involved, whereas in the scalar case, the result more easily be expressed in terms of the system parameter a.
Since the optimal choice for h is determined by balancing the trade-off between the two terms above, Ej for the approximation error and Eg for the variance, its expression is analogous to the scalar case, as shown by the following corollary.
Corollary 3.5 (Optimal step size vector case). Under the assumption that B > 1, the optimal step-size for the vector case is given by
ht hB))= = BI+CH(MOOUT
1/3
TB-1/3 B-B3/
(C((A)+Ca(NDCTT)
The constants in Corollary 3.5 are the same as in Theorem 3.4.
3.2 Infinite-Horizon Setting
The main characteristic of the finite-horizon setting is the trade-off between approximation and estimation error. Recall that in the infinite-horizon setting (r = oo), the estimation horizon T < co becomes free variable that is chosen by the experimenter to define the measurement range [0, 7]. Consequently the mnean-squrred error of the -onte estimator suffers an additional truncation error from using finite Riemann sum with N T/h terms as an approximation to the infinite integral that defines the cost Voc. More precisely, we decompose the expected cost Vo0 VT+ Vr, where V fo¹ ''E(x" (t)]dt as before, and
Sf 7 "E [x² dt
02TT
1
2aT
Vr
(11)
2a
log (7)
log (7) 2a
is a direct calculation based on Lemma A.1 in Appendix. Thus the mean-squared error becomes
MSE (h, B,T) = (B(( V = MSEr(h, B) - [vr(h) Vir] Vr. + V7.00 (12)
where MSE₂ (h, B) E (Var Vr) the mean-squared error of discounted finite-horizon setting. Note that the term V.2.0 is neither controlled by small step-size nor by large data budget B, hence results in the truncation eπror from finite estimation. Fortunately, geometric discounting ensures that V2 = O(?²T), which not unexpected given that the term constitutes the tail of the geometric integral. In particular, setting T = c log log(B) (B)llo((1/n) for large enough e > 1 ensures the truncation error is below the estimation variance. We summarize the result in the next theorem.
Theorem 3.6 mafinitehhorizon discounted MSE). In the mean-squared error of the Monte-Carlo estimator is
MSE (h, B,T) - 1 0 -hhhh + +
(13)
LB
144
where we let C(a,7) lor/)) and assume that nT = o(hi))

---

The proof is provided in Appendix B.5. It follows that the optimal choice for the step-size is (B, = (36T C)a,,)/B) The minimal mean-squared error is &S .T, B) I + Lastly, remark that if - is treated constant, the cross term (h) - Vr] Vr in Equation (12) introduces a dependence of order O(hy²T) to the mean- squared error. In this case, the overall trade-off becomes MSE (h, B, = (1I((BB) + - (1+ h)). and the optimal step-size is h" = B-1/2
O((TC(a,))BB))
Vector Case Similar to the finite- hottehooizonn setting, we establish tight bounds for the MSE in the general case involving stable matrix A. The detailed results are presented in Appendix C.3. As before, the MSE for the vector case can be computed in closed-form assuming that A is both diagonalisable and stable. The result reflects the same behaviour in the scalar case. Conveniently, the MSE in Theorem 3.6 has been expressed with sharp terms in h and B, while confining the dependence on the system parameter within the constant C, and the impact of higher-order terms in T within or This allows us to state the vector case result in a similar form, where the constant will now depend the eigenvalues of the matrix A, as well the discount factor 7. These are provided in full detail in Appendix C.2.
Corollary 3.7. For A diagonalisable, with eigenvalues given by A, the mean-squared error of the Monte-Carlo estimator in the infinite-horizun discounted setting is
T
0
MSE (h, (,), - C3o
1 (h + B 144 12 0
hB
with constant C3- C3 7) and under the assumption that y = (ht).
The terms in Corollary 3.7 correspond to estimation error, approximation error and truncation error, mirroring the scalar scenario. The optimal step-size exhibits the same dependencies on T and B as in the scalar case, albeit with a different constant dependent on the eigenvalues.
From Linear to Non-Linear Systems: A Numerical Study
The trade-off identified in our analysis suggests that there exists optimal choice for temporal resolution in policy evaluation. Our next goal is to verify the trade-off in several simulated dynamical systems. While our analysis assumes a linear transition and quadratic cost, empirically demonstrate that such a trade-off also exists in nonlinear systems. For our experimental setup, we choose simple linear quadratic systems mirroring the setting of Section as well as several standard benchmarks from Gym [Brockman et al., 2016] and MuJoCo [Todorov et al., 2012]. Our findings confirm the theo- retical results and highlight the importance of choosing an appropriate step-size for policy evaluation.
4.1 Linear Quadratic Systems
We first run numerical experiments on the Langevin dynamical systems to examine the behaviour of the trade-off identified in our analysis. The results are shown in Fig. 1. For these experiments, fix the noise 2² = 1 and the cost Q J. The lines in the plot represent the sample mean (Vs, (h) V22 and the shading represent the standard error of our sample means, computed over 50 independent runs. The plots in Fig. 1 exhibit clear, U-shaped trade-off, predicted by theoretical results.
Fig. (a) shows the MSE a one-dimensional system with T and a = 1. The ground truth V is calculated analytically by using Fq. 21 in the Appendix. The figure illustrates how the error changes as we vary the data budget, B = {2 211 214, 215 216], and also illustrates the improvement that can be obtained by increasing the budget. As increase B, both the error and the optimal step size h", decrease. This result strongly aligns with the analysis shown in Theorem 3. and Corollary 3.3. The same analysis is performed with respect to the parameter while fixing the data budget, in Fig. 1(b). By increasing the absolute value of the drift coefficient, the diffusion has a smaller impact, thus trajectories have less variability. This leads to smaller h" for the optimal point of the trade-off off.
Fig. 1(c) and ((d) present the experimental results for both undiscounted finite horizon and dis- counted infinite horizon multi-dimennional systems. For the finite-horizon setting, V is computed by numerically solving the Riccati Differential Equation; while in infinite-horizon, is calculated through Lyapunov equation using standard solver. In our coltii-dimessoonal experiments, set the
7

---

T=8,a=-12 a=-1.0
T=B, B-16384
10a
10"
(Watt)) - Vpp
10a
10"
30-1
10-2
10"4
16384
10-1
1-20100
10
10
10
10a
10
10
10
10
107
h
(a) 1, finite horizon, vary
(b) n 1, finite horizon, vary a
T=2, B-16384
T=20, B=32768, 0
10
(Vw(h) VV
10-1.
10k.
(Vith)
100
10-3
10-7
10-1
10"
10
10
10-1
10
(c) 72 3, finite horizon
(d) n 3, infinite horizon
Figure 1: saaare error trade-off in linear quadratic systems of different dimension n. The first two plots show the dependence of the optimal step-size on the data budget B and drift coefficient respectively. A 511,233,4,55 in the last two plots are random matrices and the two sets are not equal.
dimension n 3. We fix all parameters and run our experiments for 5 randomly sampled 3 x 3 dense, stable matrices in each setting. More details on the matrix structure can be found in Appendix D.1. Results in both plots suggest that the impact of the eigenvalues of A on h² is mild and that the gggenvalue-depenennn constant terms in Corollary 3.5 only marginally affect the optimal step-size h", similar to the trend observed the scalar case with parameter a. In the infinite horizon system, the horizon needs be large enough manage truncation error while simultaneously being small enough to collect multiple trajectories. We choose large enough such that a good estimate of V can be obtained, and set T = 1/(1 7), which referred the effective horizon in the RL. literature.
4.2 Nonlinear Systems
Many nonlinear behaviors can be approximated by a high-dimensional linear system, which would be bounded by our theoretical results the general case of n-dimensional systems, hinting that similar trade-offs could characterize nonlinear systems as well. We empirically show that the trade-off identified in linear quadratie systems carries over to nonlinear systems, with more complex cost func- tions. We demonstrate in several simulated nonlinear systems from OpenAl Gym [Brockman et al., 2016], including Pendulum, Bipedal and six MuloCo [TTodoovv et al., 2012] environments: InvertedDoublePenddlle
Pusher, Swimmer, Hopper, HalfCheetah and Ant. We note that the original environments all have fixed temporal discretization öt, pre-chosen by the designer. To measure the effect of h, we first modify all environments to run at a small discretization öt = 0.001 as the proxy the underlying continuous-time systems. We train a nonlinear policy parameterized by a neural net- work for each system, by the algorithm DAU [Tallec et al., 2019]. This policy is used to gather episode data from the continuous-time system proxy intervals of 86 0.001 which are then down-sampled for different h based on the ratio of h and 8t. The policy is stable in the sense that it produces reason- able behavior (e.g., pendulum stays mostly upright; Ant walking forward: etc.) and not cause early termination of episodes (c.g., BipedalWalker Walker does not fall), in the continuous-time system proxy. The results of the MSE of Monte-Carke policy evaluation are shown in Fig. Similar to the linear systems case, we vary the data budget B and see how the MSE changes with the step-size h. The MSE shows a clear minimum for choosing the optimal step-size h², which generally decreases as the data budget increases. We slightly abuse notations by using V. V to refer to the true and estimated sum of rewards instead of the cost. The true value of V is approximated by averaging the sum of rewards observed
8

---

Perdalumidd Tw10
Sipedaiia Kerwo, T-30
Inverted veettedootdeeernia www.eeeerrndd.o ums2, Tw50
Rysterww, T
3P
Upe
12"4
10-
10-
Swimmer-d, Te40
Hosparaa, Tw1
na ICheetahid, Tw50
Antira, T=10
10-
39-
122
187
38
Sample Budget
8g 2 Ba
5 8g
10 x Bo 20 Bo
40 Ba
MSE of Monte-Carlo policy evaluation in nonlinear systems. The line and shaded region denote the sample mean and its standard error of (h))())- from 30 random runs. T is the horizon in physical time (seconds). Bo denotes the aivironmenn-deeeeddet base sample budget, chosen such that it gives full episode for the smallest (see Appendix D.4). The optimal step-size generally decreases as the data budget increases (with InvertedDoubleeennduuu
Figure 2:
being the only exception).
at 8t = 0.001 from 150k episodes. These environments fall under the finite horizon undiscounted setting. The system (and estimation) horizon T of our experiments is chosen to be the physical time of 1k steps under the default òt in the original environments (with the exception of 200 steps for Pendulum and 500 steps for BipedalWalker). Please refer to Appendix D.4 for more implementation details, including the setup of B, T, 8t, h, training, and the compute resources. These systems are stochastic in the starting state, while having deterministic dynamics. Despite the different settings from our analysis, a clear trade-off is evident in all systems. This suggests that our findings may have broader applicability than the specific conditions under which our theoretical analysis was established.
4.3 Guidelines for Setting Step-Size h
The precise characterization of the MSE in Section 3 can be exploited to set the step-size close to the optimal value without any prior knowledge of the system, provided experiments on a smaller data budget are performed beforehand. Although the optimal step-size h² clearly depends all quantities characterizing the dynamics and the policy, the technical analysis of the MSE accurately quantifies how h" scales with respect to the data budget B. Specifically, h² (B) Re B-133 for finite horizon and h" (B) x e₁ B-15 for infinite horizon, where OF and cy hide the dependencies on the system parameters, exposing only the order in B. This allows us to extrapolate the optimal step-size for the given data budget, using the constant estimated with a smaller one. By evaluating through numerical experiments the performances of different step-sizes on the reduced data budget, is possible to identify an approximate ht", and subsequently determine Gp or Cy, which then gives the whole range of optimal values of l with respect to B through the aforementioned relation. Note that this approach does not require prior knowledge of the dynamics, yet it provides a systematic way for setting the step size h for any given scenario.
1/3
1/5
Figure plots the empirical h² over B for all nonlinear environments, and fitted lines based on the relation from the analysis h- = B c-/31 where the constant of varies with the environment. The plot shows that the scaling of ht w.r.t. B predicted by our analysis is overall a good approximation of the trend observed in the experiments with nonlinear systems, except for negative cases like the Inverted- DoublePendulum. This suggests that setting the step-size according to the anal- ysis can yield value close to optimality.
Atbul
Figure 3: Empirical h² in nonlinear experiments (solid) compared with analysis Corollary 3.5 (dashed): h² B-133 1/3 OF is estimated from data by least squares.

---

5 Conclusions
We provide precise characterization of the approximation, estimation and truncation errors incurred by Monte-Carlo policy evaluation in continuous-time linear stochastic dynamical systems with quadratic cost. This analysis reveals a fundamental bias-variance trade-off, modulated by the level of temporal discretization h. Moreover, we confirm in numerical simulations that the analysis accurately captures the trade-off a precise, quantitative manner. We also demonstrate that the trade-off carries over to non-linear environments such the popular MuJoCo physics simulation. These findings show that managing the temporal discretization level can greatly improve the quality of Monte-Carte Carlo policy evaluation under a fixed data budget B. These results have direct implications for practice, as it remains common to adopt pre-set step-size regardless of the data resources anticipated, which we have seen is highly sub-optimal approach for a given budget.
The present work serves as a first step toward understanding the effects temporal resolution on RL. There are several limitations that we would like to address in future work. Our analysis is restricted to Monte-Carlo estimation, while there are more advanced techniques such as temporal difference learning and direct system identification, which may exhibit different behaviours. Also, our focus is policy evaluation. It is worth studying policy optimization to understand the full control setting, which might require relaxing the stability assumption the closed-loop system since the controllers being iterated might not always be stable. Additionally, it would be interesting to explore non-uniform discretization schemes, such through adaptive sampling scheme. From the system's perspective, we have currently analyzed stochastic linear quadratic systems with additive Gaussian noise and noiseless observations. It remains to be determined if the exact characterization is still attainable with other types of noise, in the partially observable case, or with noisy observations. Finally, extending the analysis non-linear systems would be valuable.
Acknowledgments and Disclosure of Funding
The authors would like to thank Csaba Szepesvari for the helpful discussions. Zichen Zhang gratefully acknowledges the financial support by an NSERC CGSD scholarship and an Alberta Innovates PhD scholarship during this project. He is thankful for the compute resources generously provided by Digital Research Alliance of Canada (and formerly Compute Canada), which is sponsored through the accounts of Martin Jagersand and Dale Schuurmans. Dale Schuurmans gratefully acknowledges funding from the Canada CIFAR AI Chairs Program, Amii and NSERC. Johannes Kirschner gratefully acknowledges funding from the SNSF Early Costdoc.Mobilljg fellowship 22EZP2_19978.1
References
Y. Abbasi- Yadkori and C. Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In S. M. Kakade and U. von Luxburg, editors, Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 1-26, Budapest, Hungary, 09-11 Jun 2011. PMLR.
Y. Abbasi Abbasi-Yadkori, N. Lazic, and C. Szepesvári. Model-free linear quadratic control via reduction to expert prediction. In The 22nd International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2019.
Bahl, M. Mukadam, A. Gupta, and D. Pathak, Neural dynamic policies for end-to-end sensory motor learning. Advances in Neural Information Processing Systems, 34, 2020.
L. C. Baird. Reinforcement learning in continuous time: Advantage updating. Proceedings of 1994 IEEE International Conference Neural Networks (I4, volume 4, pages 2448-2453 IEEE, 1994.
M. Basei, X. Guo, A. Hu, and Y. Zhang. Logarithmic regret for episodic continuous-time linear- quadratic reinforcement learning over finite-time horizon. Journal of Machine Learning Research, 23(178):1-34, 2022.
E. Bayraktar and A. D. Kara. Approximate Q-learning for controlled diffusion processes and its near optimality, 2023.
10

---

H. Bijl, J.-W. van Wingerden, T. B. Schön, and M. Verhaegen. Mean and variance of the LQG cost function. Automatica, 17:216-223, 2016.
S. Bradtke. Reinforcement learning applied to linear quadratic regulation. In S. Hanson, J. Cowan, and C. Giles, editors, Advances in Neural Information Processing Systems, volume 5, 1992.
S. Bradtke and M. O. Duff. Reinforcement learning methods for continuous-time Markov decision problems. In Advances in Neural Information Processing Systems, 1994.
G. Brockman, V. Cheung, L.. Pettersson,, Schneider, J. Schulman, J. Tang, and W. Zaremba. OpenAl gym. arXiv preprint
2016.
K. Burns, T. Yu, C. Finn, and K. Hausman. Offline reinforcement learning at multiple frequencies. In Conference on Robot Learning, pages 2041-2051. PMLR, 2023.
T. Cao and A. Krishnamurthy. Provably adaptive reinforcement learning in metric spaces. Advances in Neural Information Processing Systems, 34, 2020.
W. Dabney, G. Ostrovski, and A. Barreto. Temporally extended e-greedy exploration. In Proceedings of the International Conference Learning Representations, 2021.
Dean, H. Mania, N. Matni, B. Recht, and S. Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, 31, 2018.
S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-677 2020.
K. Doya. Reinforcement learning in continuous time and space. Neural computation, 12(1):219-2455 2000.
C. Eliasmith and P. M. Furlong. Continuous then discrete: A recommendation for building robotic brains. In Conference on Robot Learning, pages 1758-1760 1763. PMLR, 2022.
M. Fazel, R. Ge, Kakade, and M. Meshahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning, pages 1467-1476. PMLR, 2018.
T. T. Georgiou and A. Lindquist. The separation principle in stochastic control, redux. IEEE Transactions on Automatic Control, 28(10)44481-2494, 2013. doi: 10.1109/AA..21132225222
Gu, Lillicrap, I. Sutskever, and Levine. Continuous deep Q-learning with mosel-based acceleration. In International conference machine learning, pages 2829-2838. PMLR, 2016.
Y. Huang and Q. Zhu. Infinite-horizon Innea--quadratice-aasiiiaa control with costly measurements. arXiv preprint arXiv:2012.14992 2020.
Y. Huang, V. Kavitha, and Q. Zhu. Continuous time Markov decision processes with controlled ob- servations. 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 32-39. IEEE, 2019.
Y. Jia and Zhou. Policy evaluation and temporal-diiee -iffereeeeeeeeeeeeeeeeeeeeeeeeee learning continuous time and space: A martingale approach. Journal of Machine Learning Research, 23(154): 2022a.
Y. Jia and X. Y. Zhou. Policy gradient and actor-critic learning in continuous time and space: Theory and algorithms. Journal of Machine Learning Research, 23(154):1-55, 2022b.
J. Kim, J. Shin, and I. Yang. Hamilton-Jacob deep Q-learning for deterministic continuous-time systems with Lipschitz continuous controls. Journal of Machine Learning Research, 22, 2021.
K. Krauth, S. Tu, and B. Recht. Finite-time analysis of approximate policy iteration for the linear quadratic regulator. In Advances in Neural Information Processing Systems 32. 2019.
A. Lakshminarayanan, Sharma, and Ravindran. Dynamic action repetition for deep reinforce- ment learning. In Proceedings of the AAAI Conference Artificial Intelligence, 2017.
11

---

J. Lee and R. S. Sutton. Policy iterations for reinforcement learning problems in continuous time and space fundamental theory and methods. Automatica, 126, 2021.
F. I.. Lewis, D. Vrabie, and K. G. Vamvoudakis. Reinforcement learning and feedback control: Using natural decision methods to design optimal adaptive controllers. IEÉE Control Systems Magazine, 32(6):76-105, 2012. doi: 10.1 21110//C...001..22211
A. Lindquist. Linear stochastic systems. SIAM Review, 32(2):325 -28, 1990. doi: 10.1137/1032067.
M. Lutter, S. Mannor, J. Peters, D. Fox, and A. Garg. Value iteration in continuous actions, states and time. In Proceedings of the International Conference on Machine Learning, 2021.
M. Lutter, B. Belousov, S. Mannor, D. Fox, A. Garg, and J. Peters. Continuous-time fitted value iteration for robust policies. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2022.
A. M. Metelli, F. Mazzolini, L. Bisi, L. Sabbioni, and M. Restelli. Control frequeney adaptation via action persistence in batch reinforcement learning. In Proceedings of the International Conference on Machine Learning, 2020.
F. Mezzadri. How to generate random matrices from the classical compact groups. arXiv preprint math-ph/0609050, 2006.
R. Munos. Policy gradient in continuous time. Journal of Machine Learning Research, 2006.
R. Munos and Bourgine. Reinforcement learning for continuous stochastic control problems. Advances in neural information processing systems, 10, 1997.
S. Park, J. Kim, and G. Kim. Time discretization-inaarin safe action repetition for policy gradient methods. Advances in Neural Information Processing Systems, 34, 2021.
S. Sharma, A. S. Lakshminarayanan, and B. Ravindran. Learning to repeat: Fine grained action repetition for deep reinforcement learning. In Proceedings of the International Conference on Learning Representations, 2017.
S. R. Sinclair, S. Banerjee, and C. L. Yu. Adaptive discretization for episodic reinforcement learning in metric spaces. In Proceedings of the ACM Conference on Measurement and Analysis of Computing Systems, 2019.
R. Sutton, D. Precup, and S. Singh. Between MDPs and semi-MDPs: framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112:181-211, 1999.
C. Tallec, L. Blier, and Ollivier. Making deep Q-learing methods robust to time discretization. In International Conference on Machine Learning (ICML., number 97, pages 6096-6104, 2019.
E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physies engine for model-basee -baed control. In 2012 JEEE/RSJ international conference on intelligent robots and systems. IEEE, 2012.
S. Tu and B. Recht. Least-squares temporal difference learning for the linear quadratic regulator. In International Conference on Machine Learning. pages 5005-5014 4. PMLR, 2018.
S. Tu and B. Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. In Conference on Learning Theorry pages 3036-3083. PMLR, 2019.
P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. van der Walt. M. Brett, Wilson, K. Millman, N. Mayorov, A. R. J. Nelson, F. Jones, R. Kern, E. Larson, C. J. Carey, i. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, Perktold, R. Cimrman, I. Henriksen,
A. Quintero, C. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17: 261-272, 2020. doi: 10. (038//41192-0199) 09-0119-666-2
H. Wang, T. Zariphopoulou, and X. Y. Zhou. Reinforcement learning in continuous time and space: A stochastic control approach. Journal of Machine Learning Research, 21 (1(18)) 2020.
C. Yildiz, M. Heinonen, and H. Lähdesmäki. Continuous-time model-based reinforcement learning. In International Conference on Machine Learning, pages 12008-12018, PMLR, 2021.
12

---

Appendix
A Moment Calculations
Recall that the solution of the SDE in Equation (7), with (0) 0, takes the following form:
x (1) - / call-a) dw (s).
(14)
An integral part of finding the mean-squared error the Monte-Carlo estimator is the computation of the moments I [xx()²] [xt) and E [=(s)2x(t)²] when
Lemma A.1. Let zt) be the solution of Equation (7). The second moment of the state variable is
0² (c2nt - 1)
E [(2²(t)]
(15)
2a
For the fourth moment, we ger:
30
E x (t)
(c2at - 1)
(16)
4a
Assuming that s S t, we further get:
E(
(c.as - 1)e {(e-2us 2as -a- ) + 3(1 - c22as)
(17)
4a²
Proof.
(1) We start with the second moment E [zx()
2atE ( c (ddd)) dro(s)
| o² o²2aat (" c 2ax ds
0²
E [xt)t]]]
e
(e 1)
2a
The calculation makes use the Itō isometry, which can be stated as:
E [ =ss) dw (8) ( - E [ 2(8) ds
(18)
for any stochastic process z(.) adapted to the filtration induced by the Wiener process (+).
(2) Next we compute E [=(1)]] through Itt's formula. Define y (1) = fo e-s du (u), so that
dy (t) aat dw (t). Thus,
af (f dy()) 5 (v))) dy (t))²
= f' (v (t)) du (t) , (t())) e 2nt dt,
for any (-). By choosing / (v) =
f' (v) = 4y and f (v) = 12y².
13

---

Therefore, by integration and taking the expectation:
L. f' (y (u)) e dw (u)
Lo
Bf (y (t)]
=E
E
f
(y (u))
e
2au du
IE !." (1o e-a dw (t) an du (u)
[o e e-a dw (0) )
+ 22 B
12
2an du
0
L av e dw (0)
6E
du
e) du
6
eave-au au dw (1)
(Itō isometry)
e- 200e e-aw 2au du du
1
2nu
(1 - 2au) du
0
2a
3
2at)
4a
From Equation (14) it holds x (t) = ge (t) so that the second part of the lemma follows.
Lastly, we compute [=<s)2<(tt²] for St.
(%/ e dw (u) )² (fe
27 )
(s) x² (t)] = o² 20(
e -au dw (u)
(J² e dw (u)
(Jo E au dw (u) + f" e-aw dw (u)
σ 20(
(J" e an dw (u)
27
o 20(s+e)
E
e am dw (w)
+
e an dw (u))
i
(18)
Note that we computed (i) before. For (ii) it holds:
[1, c-a dw (u)
/ 2au du
1
(1
22s
2a.
and
( e au dw (u)
l" e
2au du
=
1
(e-2as -2at)
2at
2a
Therefore, assuming < t, it holds that:
E 2 (s) (1) o _ 2a(++)
2a (1 c -2s)) (e (c-2as - -E-2at
1
(1 e 2as)
22a0
+ 4a
(c2at 2as {(e-2at - -e-20s) + +(11- c -2at]
4az
14

---

B Calculations of the Mean-Squared Error
B.1 Undiscounted,
Proof of Theorem 3.1
Proof. We first note that
N-1 Bix (kh)) h
N-1
[[V)(hh] M
Σ (()))(h))
E
where we denote sx(t) x1 (t) for simplicity. Next expand the mean-squared error 2V (h)] + +V
(A) VT) 3 (h)]
h
(((0))
2VTTB[(N(()] 1 +
E
M
1
N-1
Blo)
2V7BIVA (h)] V2
M
(-j= k,1=0
122
M - M
2
[ 2V> V?
M
M
8,1=0
For the last equality, note that o (A)) It remains to compute the expressions. By Lemma A.l we have for the second moment of the state variable:
[t)
(E2at 1)
(19)
2a
Assuming that S t, from the same lemma we get the following for the fourth moments:
o+ (c 2as 1)e2at {(c 2as -2tt) + 3(1 -2as))
E[x 2(x2(s)x² (s)x²(1))
(20)
4a
Note that by symmetry, a similar expression follows for 2 t. Using these expressions, for the expected cost get
0² 1/" (e2at 1) di 2a
0² ( -
VT
E (()
T
(21)
2a
2a
We remark that similar expression was previously obtained in [Bij] et al., 2016, Theorem 3]. Next, the expected estimated cost
B[VaN (h)] = h Σ Bla²
N-1
o²h
Σ
(e
2ahh
1)
2²h
1
T
N
2a
2a
2ah
0
km
Lastly, it remains to compute the sum
2
N-1
E El((( 212 N-1
122 N-1
Σ
Σ
E
[khi)
M
M
M
k,1=0
k<1
k=0
TT 112 (caaT - 1) 2ah + 2aT + 1) + 2 (c 1) 2
2hT (c2ah 1) (c2ah 5C
4a Bh (eZah 1)²
The last equality is cumbersome calculation that involves nested geometric sums. We verified the result using symbolic computation. For reference we provide the notebooks containing all calculations in the supplementary material. remains to collect all terms to get the final result.
Proof of Corollary 3.2. When a = 0, the Langevin equation 7 is reduced to dz(t) = a dw((). The computation of MSE can be performed similarly to that the proof of Theorem 3.1, by using the following moment results of Wiener process.
[[r+(t)]=o²tt
(s)r()) s((t + 25) when St.
It remains compute the sums, and collect terms, in the proof of Theorem 3.1.
15

---

It is also worth pointing out that the result of Corollary 3.2 can also be computed by taking the limit of the MSE in Theorem 3.1 when - O. And the resulting MSE from the limit matches the one computed directly as in the proof above. This shows that the MSE in Theorem 3.1 is continuous at
B.2 Undiscounted, Finite-Horizon: Approximate MSE
Proof of Corollary 3.3. For the asymptotic expansion, we use Theorem 3.1 to compute the leading terms in of the mean-squared error:
o ( - 1)² h + O(hi),
En (h, T.a)
(22)
16a
(h T,a)
T'T (4aT AaT + 2a (8aT 44 5)
1
a TT(1
eooI
+
B
Sa²
1B
403B
T'Th (1 4o' + 20T (8a'l + 4) - 55ta")
o
o'Th3( - -1)
O (h²) (1//B))
24a B
12aB
(23)
Next, we compute explicit upper and lower bounds on the MSE that hold for any h and B. Note that for all x < 0,
22/45 (-I+e" - 1)²
x² 1 1)2
(24)
Hence we can directly bound the E1 term from Theorem 3.1:
A4 (e he - 1)2 04h3(eaT - 1)²
2a221? - 1)²
< Es 4
64a1
16a
16a1
To bound EA₂ note that for x S 0,
x² S (1 - e7) 11 2
(25)
x²
Abbreviating E3 = (62eT - 1) (4e 2aT + 1) - (e2ah -1) (e2ah + 46 + 1) T, we have
Eg
TTE 2n (1- and hence
Ba TTT- Es S E 1+
Sa'Ri²2 EE o
To upper bound Eg, we repetitively use that for all 50.1+15 e² $1 x² 1 + + 3 Se
2 and
E3 h (c - 1) (4c caaT 2aT +1 - (c2ah - 1) (c2ah + 4c + +1) T
4ho 2ah + dall 2he
Tedah 4T 2a 2a2 +T
= M(e2aa(Ae22 2aT - 44 + te LuT - 1) 4Te 20T 2ah lah + 2oT +T
4 212133 ) 20T 44 + AaT-11 -1)
S <h((1 + 2ah + 212 + 3/50
4
32
2aT (1 + 2ah + 2a"h2
+
-a3h1) -T(1 + 4ah + -0222²
a a²(133) ) 4T 20T + T
3
3
h(462aT 5 AoT
Sal'e 20T 4Taa + (2
(4e 20T -) 888- 2T 2aT 8821)
16
32
16
+ +8a 1)
a
3T
2aT
a.
+ h²a
(62aT' 1) 1)
3
3
< h. 2aT - 5 + e AoT
SoT 2oT
4Ta) + 12
AT3
16h 272
3
Combining the last two displays yields the claimed upper bound. The lower bound follows along the same lines. Note that the bounds can be refined by including higher-order approximations of ex.
16

---

B.3 Undiscounted, Finite-Horizon: Optimal Step Size
Although the exact optimal step size h" can be obtained from Theorem 3.1, such exact ht doesn't have an explicit analytic solution in general. Numerically, we can find ht by searching over step-sizes hmm- = T/ 7/m for m = ,,.... B, provided knowledge of the system parameters a and fixed horizon T or, by finding the root between 0 and of the following equation
55 + 4aT 2 (4+ e SaT) ( + 37) + 2a 2a 5a + 288'T + 56aTe 2a?
-32, 202) + 2 (3 - 1)2 + a 7e 4a + 60aT 120aTe 84620l) )] =
where the equation is simplified form of a öh (h,
From the analysis point of view, a trivial way see the order of h- in terms of B, a, T is finding the dominated term by using Taylor's expansion for exponential parts (which is true for any h)) in Theorem 3. Such asymptotic expansion is given in Corollary 3.3. is immediate that for h 2 1, both Equation (22) and Equation (23) will blow up. Thus, a small h < 1 is considered to minimize
Ei (h, T, a) (x)) Keeping the first term in both Equation (22) and Equation (23) and solving for the optimal h* yields the result in Equation (10).
A more precise approximation of ht than Equation (10) is a minimizer of E, T,, a) + T. truncated at (h²)):
+
D1
D
3D2
9D3
D2
h² ha T,
3Dg
D
2a D3
V
daaDz
9a D3
D
3D2
9D3
D2
+
(26)
3DD
202
4a D3
9a² 9a²
where
D1 = T (1 = 4aT + e 20T (80T + 4) - 5c Au'))
D2 T (4aT e AuT 2oT (8aT 4) + 5)
D3 = BB - 1)2 4aT AAT 1)
We can further express Equation (26) in terms of B,
1/3
T - - AaT + 2aaT (8aT - 4) + 5)
1²B)==
B B-1/3
a a2(220T - 1]2
T (1 + 4aT + 2al (8aT + 4) - 10
4aT + 1)D2 1/3
B
9(c2oT 1)2B
9/2/3 (a2/3(c2aT
(2a0 - 1)533
(e 11 B- O
27 - 1}3
where the first term is exactly the result in Equation (10).
B.4 Finite-Horizon, Discounted
As stated in Section 3.1, adding discounting in the error more involved. In the regime where h small and B is large, Taylor expansion characterizes the error surface as follows:
setting makes the mean-squared
2T22T(22TT -1)2
MSE; (h, B,T)
lag(7)(a+ + (2g a + log(>))) hB +
h22
16a2
otaI (e2aT 1) (3² (e2eT (2a + log (7)) log (7)) - -2a)
133 + 0 h4
48a
144
(27)
17

---

The approximation shows only the lowest order terms for 1/(hB), y" and h. The derivation is given in Lemma B.1 below. The results shows that main trade-off between h and B persists also for the discounted objective, as long as y is treated as constant relative to h and 1/hB. In the limit where y becomes small (e.g. error improves to Ohh)). This can be understood from the fact that under geometric discounting combined with a decaying process, the sum of N = T/h estimation errors do not suffer a factor N, thereby removing factor of 1/h from the (non-squared) approximation error.
o(h²)) the nature of the trade-off changes that the approximation
Lemma B.I (Finite-horizonn discounted). In the finite-horizon with discount facior 7 (0, setting, the mean-saaaan squared error of the Monte-Carle estimator is
MSE (h, + Ez(h, T, T,
where
1 + Ca(Timaa) +0
Ei, = C, h²2 C2 + 144
(T + Ca
T,,,, = log(7) log(:)) (og +7)0(1),
22 (2207-1)² 1)²
CTT,,T,))
16a²
C2(T,7,a) 7" (c2aT (7T (e2aT (2a + log(n)) - log(>)) 2a)
48a2
7-t 7" (620l (2a + log(7)) log(>)) 4a (c202 (2a + log(7)) -og(7))
C,(T,r,a)=
576a²
CT n,a) some finite constant of (T, y, a) that includes 7f as a factor.
Proof. The proof follows the similar computations as those in the previous proof with a new expected cost as follows. particular, using Lemma A. we get
VT L/ 7 1
a² ( T2aT
TT - log(7)
(28)
2a
log(7)
+2
Furthermore, the expected estimated cost is
h2h kh (22akh - -1)
02h
(1 72th 22a'l'
1 7"
([)) = 2a k=0
2a
Finally, the sum containing the fourth order cross-moments is
122
2h2
N-1
h
N-1
(le))) = M
( + kei
Σ k=0
7 2kh (kh))
M
M
0,1=
While not impossible to calculate on paper, a written derivation is beyond the scope this work. Instead, we rely on symbolic computation obtain the expression and corresponding Taylor approxi- mations. The notebooks containing all derivations are provided in the supplementary material. O
B.5 Infinite Horizon: Proof of Theorem 3.6
Proof.
The proof relies on the decomposition provided in Equation (12). It only remains to compute the following cross term.
E (ha(h) - Vi
Vr
ot
75
TT Te20
h1
TT 2aT
1 1- 1-
1 (TT'2at' - 97-11
2a
(og(())
log(>) +
2a
7th e2ah
1 7/h
2a
log(?) + +2a log(7)
a 2T
(62aT 1) (log(7) (220T
-1) 2a) h+
8a² log(>) (2a + log(?))
TAyT (2a+ + log(7) 2a7 log(?)) (2a (yT eaT - 1) + 7 log(7) (c2TT-1) h²2 O0h3).
48a² log(?) ( (2a log(>))
18

---

Thus, the mean-squared enror MS (,T,)) - E (VM (h) - Voo] is obtained by combining the above computation with Equation (11) and Lemma B.I.
is worth pointing out the trade-off always exists with or without the assumption y" = o(h²) from MS B, r)) For example, if 7 is constant with respect to h,
T'T MSE B,T,)
log(7) + (oogo)))(())))) 1og(7))² hB
ot o (e2aT 1) (log() (7) (c2aT - -a) 8a² log(7) (2a + log(>))
S 2²aT) log(n) + 2a|²
+ +(hh))+
4a (lo(()))) + log(n)))
this case. For the other cases of y MSE (h, B, T, 7) can be obtained similarly by combining the cross term in the proof of Theorem 3.6, Equation (11) and Lemma B. The case where >" (h*) particularly interesting
From the above expression, MSE (h, B, T) contains constant
because even as y + 0 at such fast rate, there is still trade-off that never vanishes.
C Vector Case Analysis
C.1 Finite-Horizon, Undiscounted: Proof of Theorem 3.4
Proof. Consider the n-dimensional system that the solution of the trajectory of X()) is
x(t) = = A(l-s) aw (t).
Since A is a diagonalizable matrix, we can decompose as A P-1DP, where is invert- ible matrix (not necessarily to be orthogonal) and D is diagonal matrix whose diagonal entries (A An) are corresponding to the eigenvalues the matrix A. Followed by which, we can decompose the matrix exponential of A as:
At = P-
Define the "diagonalized" process X (+) as:
PX (t) = Po Alc-o) dw (s)
=oPp-1 ( (( PWW dw) (s)
a I D(t-s) aw (s) = (1)
where W. (s) a Wiener process (with dependent components when P not orthogonal). This implies that X (-) = P-1 x (.).
To (t) clearly, denote P [p,, and Xt(t) (t) (c) then o00 (t) Σ Pijor So cc((-=)) (
(s) for each I f1..... n). Particularly, in such expression, wy (1)
(s)
are independent Wiener processes for different i j. Correspondingly. (t) = (ti ... on ( and (t) E Piyor 1o' (tr(t=>) dwy(s) for each e (1...., .n), where wy (s) independent
Wiener processes for different j.
19

---

By trace operation, we can rewrite (hr as follows:
N-1
Vhr(h) - M
Σ
Σ
hx (16) (X
==1 k=
1 M N-1
1x P
= tr
M
i=1 k=0
= = PM (
where Vi (h) - 1/ Σne Σ hX (Lx) (le) (1x) E Ruxn
Similarly, V/r - tr ( ( / }. where Vr- - ] de. Therefore, the MSEr(h B) can be written
MSE, B) = E [Var (h) Vxr 21 = E tr P-TQQP-1 (D (h) - -vr)
(29)
For notional simplicity, we denote matrix P- P-TQP-1- =: B = [bb)] and Var (h) V/- =: C= [uy]ū,=1-
Noting the fact that
|
27
MSEr(h, E
Σ 1.
Σ
byn 1 Autal
(30)
it is sufficient to find MSET by only computing E [ct, Ctzjzl- We first introduce the following expectations that are used in the computations. For any
A1(t--u) du(u) ( e2a(s-u) dw(w))
(1-e-(Artian
E
(31)
S caa(o-u) du(u) ( cdslt-u) dw(u) ff cdult-w) duo(u)
e (e((--)) dw(u)
E
1
(1- (1-e-(othhio)
(A1 + ++22 + +1)
1
(1 (16--Artdb)o)) (1 -e (1--al
+ (A1 As) ha)
(1 (1-t-() (I 1-e-(ootdo)
+ (A1 + Aa)(A2 + Aa)
(1-e-(Ar+22)) (aotiiiie - -(ottooe))
(32)
(1 + 22) + Aa)
% cile-u) dro(u) 1 cda(-u) dw(()
d e(ditde)T - 1 1-11 + 72)
E
(33)
(A1 + x2
20

---

By using the definitions of VAs (h) and Vr, it is trivial to see for any L.j E {1,..., ,n}
N-
(kh) -f (lo)(t) dt
(kh)o (Kh)
Ct
hoi
M
h
M
N-1
kh
(illh--o) ds)
Σ Pja jo (
(2i(kh-s) dura"
Pla
M
k=
Pio J'" Ailtess) dwa (8)
Σ Pio Lo edi(t=os) dwca(s) ) di
0²
E
ho?
N-1
Jo kh
(%o
rhh
Σ
(lilkhho)) (s)
eds(tlo duuli (s)
PiaPjo
!'"
[[] exilt-o) dwals)) (% eds(i-o)) duaals)) dt
0²
E
ho2
M
N-1
kb 2i(hh-=s)
phn (%.m) ((s(h duo" ]
Σ
din
PlaPys
M
078
k=0
where the last equation is due the fact that for a +
E [V[ dult--s dwaa(s) (Jo )dilt=s) dup(()) ) =0. 0.
Thus, for any 4, Sr f2 E (1....,,) nn],
n Σ
E B[tti)
Pi o 'I, (M,,, T, Ar, Aii Ata A12, a))
PhaPihaPP I2 (M, h, T, A.; Aegs A33= B3 a
PhaPP.sPhaaPpso Is (M, h, T. Ar, Ajr A1 a, B),
(34)
where
I (M, h. T, dr Ag.s Al. a):
h
M
N-1
ca12 (R)--) (s) ) (1,z) Rh enn ( (wh- duol")
M
km
dt x Ao, (e-s) (e-s) dwals)) (fo cinitttss arcc(ss)
h
M
N-1
kb
ex (kh-)) dudd)(o) (1oa)) (dva(th-0) d (s)
M
K=
(1-()) dw)a(s) ) (1o edsaltto)
de) dowalss) (eso)))))))
E
21

---

and
I2 (M, h T, A1 Air
Algs Aja Or 3)
h M N-1
Jo kh
en (Kh--)) du (s) (%o
=E
Σ M
e (kt- diod
k=
[.
di (c-o) ( (%o ohullto)) dwaalo))
dt x 202 ( (kh-s) ds) (%.m) c drop
h M
N-1
M
K=
()1z(t=a) dwg((s) (% odvalt-s) dwsg(ss) dt
E
and
Ia (M, h T, Xr, Aii
Alg Ajar 0r, 13)
h
M
N-1
Ath
en (k)--)) ds)
(%.a)) edss (kh duog (s) (s)
= E
M 1=1
K=U
h
kch
(kh
duo (s)
kh
eni (Kh-s) dw (6) (s)
M
(1)
Note that wa and w are independent for # B. By using the expectations Equations (31) and (33), we can further obtain I2 (M, h, T, do, Air Aea Aizi a, B3 as
I2 ( [M, h, T, Ar, An A Aja ax 3)
(2,, yr
T
- (A1, + X3. )T)
(A + )
1 Ar thi )1
h
-
(Ae, + Agi)
h
e +d52)
T
1
(ellethia)t - (A12 + >33)))
x
(Dtz + }zz))
(Mig As2
h
(N1, + >3a)?
In the following computations, we will use C and C(A Atso A1a )12) to represent some constants that are not depending on h, T, B.
The expectation Iι (M, h, T, A,, Ar,, A32. a) is computed exactly the same way as in the proof of Theorem 1 by using the expectation results Equation (31) and Equation (32). Notice that the expectation result Equation (31) (when Moreover, the two expectations Equation (32) and Equation (17) have the same orders in s and t. Thus, I, (M, h, T, Xi, Ajr A1a: Ajz, a) has the same orders in h T, B as the scalar MSE, i.e.
f) has the same order in as the expectation Equation (15).
I1 (M, h, T, A1, A3, Aea, Ain a) (C1 + C1 (A Aj. N ),2 ((T)) T + O1h3)
3
1
(O2 + C2 (Ae, A A (n, OT))
+ O
hB B
The expectation Iz (M, h, T, A1, Ain Ao,, Asoo B) can be computed directly and has the result:
(d)), )r - 11) (eldes ((dd)ttha)l- - -1) 112 + Ohh3)
Ig (M, h, T, No, A.. Az., Aec Aj2, a, 3)
4 (Me + djz) ) (A12 + )122)
1 T2 + Ca(de, >5., Aes: Ais )=((0))))) 122 001))
1
22

---

The expectation I3 (M, h, T, A,, A3+- A12, N5,, a, can be computed as follows:
Ia (M, h T, Al., Asr A12 A3z a,
(A - kkh - 1) ( t ) - 1) h2
12
n
M
(A1 + A1a) (dis + )5z))
h?
Ax Dighhtt As hht Asght
e (21s (dra))))) (1 (1-e-(Mp eaas t -A )bh)
M
(A1s (1a) (Ai + )ia)
h
eA A 21 oh+ aht kn (1 (1-e (--e-(ee (1- e- (Ais (o2ttt))))n
M R<n
(Ar, + A1a) (1/, + +1/a)
TB
1 B
= + C1 (AL Ap Ab An) O(T))
O
hB
Thus, the final result is obtained by the expression of MSE in Equation (30), Equation (34) and the above computations. Again, we rely on symbolic computation to obtain the expression and corre- sponding Taylor approximations and include the notebooks of all derivations in the supplementary material.
The extension from Theorem 3.4 to the discounted hhite-horizon results can be done in the same way as in the above proof (add the discount factor yy in VMr) by using the expectation cost for any A and Ag:
1/"
7'' ' % (dl(e-u) du(u) l'd مسa(-w) du(w))
7tt (elltttaall -1
7"h -
(A1 22) log (7) (A1 + )2)
log (7)
C.2 Proof of Corollary 3.7
Proof. We shall follow the similar proof as in the proof of Theorem 3.4 and the proof of Theorem 3.6. Continuing from Equation (34), in aefinite-horizon discounted setting, we have
Ig (M, h T, Ad A Na. 7,
h
M
N-1
(%.ee.
eai (e (kh-a) dmw?(()) (%, Ach
kh enii edi (nh- (s)
E
7
M
i=1
k=U
Ao (e-s) (e-se))) (() (1o edualtts) dwa dlwacss) ) di
Y
'E
h
N-1
khh (L,te) (Kh dwddl
(1,m0) cdvalko-os) d dwol (6)
M
K=
1.00 ''
cdez(t-o) dwals)) (f, edialt-s)) awal(s) dt }
and
In (M.h. T, Ar, Ajso Al.. A Y,a, 9)
T Tel +22, )r
1 - 7
1
1
(11 )jn)
1 (Me ( +hin h
- Th
(Ae )zr)
log (+)
log (7) do Aos
h
- n (A12 A52)T
1 1-
1
1
1
()2 + )
(hig +>12
1 7/
(N1, + -dz))
log (7)
log (7) + diz + Axp
23

---

and
Is (M, h, T, Xr, A3
Als Azz F, a. B)
=
E
h
M
N-1
Σ
Rh
ea (kh- duod (s)
(%om)
can (&h (ah-o) due (2) (s)
x
M
==1
k=
h
Σ
Σ
kh
kh
(kth d (s)
kh
(Asa(thi-s) dwy ())
M
Similar arguments as in proof of Theorem 3.4, we can conclude I₁ (M, T, des Ais Aegs Aizo a) has the same orders in h, B, T as the MSE result in Theorem 3.6.
Moreover, let C,(A,, As. A121 A321 TY's are constants that depend on X Aisr A12 7, T, then
Ip (M, h, T, Mr, A3. Ma.
= o 002T (CI(Ac,) A121 A2 T,T) + C2(Ar, A3. Ae Aber 7, TThh
+ + (Ca(A din Alo Jo T)n + Ca(Asn A No. jo T)h²))
+ to ( 1
+ Cs( Aye 1et + 0(19),
144
and
Ia (M, T, T,,r, Ar, Aii Ala Ajzr 7: a, ()
(e()e thg )it -1 (e( + +ds 1) 122
122
N-1
Σ
M
(),, + Aca) (Air + )12))
k=0
12
Ar Ah gh+ kh+ Agah
e (12)))))) (1- -(As (Nsst)))kk)) 210t
M
(N1, + )zg) (dis )za)
2
A bht gh+ A kh
(1- 61-6 + (1 (1- (Ass (2)))21))8)) 7(0to)
M
(N,, + (1a) (Ais A1z))
k<g
T
= =Ca (Arr,)jrr Naa A52 7, I)
+
hB
B
The result in this Corollary is obtained by combining the above results. And we include the notebooks of all derivations in the supplementary material.
C.3 The case when A is a general stable matrix
Lemma C.1 (MSE when is a general stable matrix ). Let be a stable n. x n. matrix with distinct eigenvalues ' Am and corresponding multiplicities "1,".. ". -9m- There exist some constants (C.Ym Co and C,(,,... .mm Y, T) 's, such that the mean-squared error of the Monte-Carlo estimator in different setting satisfies
(1) Finite-Horiznn undiscounted setting:
MSET E
Σ C.C.MSTT Ci Am. T)
t=1
(C2 + Cs(A1, Am, (T)) o 2T2443
+ 0(13) + 0 +
(35)
Bh.
where MSFT (h, B, As) is the meenn-squree error of the Monte Morte-Carlo estimator in Theorem 3.1 by replacing the drift by Xi.
24

---

(2) Harite-oorzzon discounted setting:
MSET &.MSSEr B, Ca(An, Amx 7, T)o 2 T2?
+ Cs(A1, ... Am, 7, 7) + Co(A1, ... Am, T)o'h
+ (Tr(d,
Am y, 7,T)) 472m-1 + 0(h)) 0
(36)
Bh.
where MSEr(h, B, Ad) is the mean-squared error of the Monte-Carlo estimator in Lemma B. by replacing the drift by Xi.
(3) Infinite- Horizon discounted setting:
Infinite-Horzon
m Σ
&,C.MEE (h, i=1
(b, B,),))).
7, T) + Co(A1,'.. Am, 7, T,,Thh)'* (Ca(A1, Am; 7,
+ (C2o(A1, Am 7s T)h + Cni(A, .. Am 7, T)h²) o o'a
+ Cr2(A1 .. Am. No (Cis(A1, '. Am 7, T)) o TT
Bh
+ 0(h)) 0 }
(37)
where MSE (h, B, 7, X²) is the mean-squared error of the Monte-Caree estimator in Theorem 3.6 by replacing the drift a by X;-
Proof. As we can see the proof of Lemma B.1 is based on the proof of Theorem 3.1 with adding discount factor y, and the proof of Theorem 3.6 is based on the proof Lemma B.1 with the decomposition Equation (12). By using the same flow direction, it is sufficient show the result in case (1) and the results in case (2) and (3) follows.
Consider the decomposition of MSET in finite- haite-horizon undiscounted setting:
MSE₁ = (VM Vr
= E (Vxr E
[VM
+ EE
21 VM
- 1/]
2
E
M
VM
+
E
VMd
Vir
Part1
Pant
Before the analysis of part and part 2, we will introduce the following mean mean-squares -quared error notations for the finite-horizon undiscounted scalar case with drift A;:
MSE, (h, B, As) (ar(h, A;) + Approximation(h,, B,A:):
(38)
where Var(h, A,) = 2 - E VM 2
and Approximation(h, B,, = (B [Vs - Vir 2
For part 1:
h2
E
Σ
E
M
M
R.J.R.l
1/2
E Qx, (1, QX,(1I) (Xx, + 2tr (QE (X.(k)))x T]}
M
h22
(IX(k)TQXX(A E (Ih
k.
21/2
+ 4112 Σ tr [X(N)))))) (39)
Σ tr ((H))(())))
M
M
k
25

---

where the second equality is based on Isserlis' theorem and the trace operation.
Notice that E
Vis
Ex E [x(II) QIh)
thus
[is] 1
E
2
E
M
2h M
4h2 M
Σ tr (QE (((A))(()()) K
Σ tr K<!
To analyze the above form, we decompose the matrix A by it Jordan form, i.e. A = PP for some inevitable matrix and J diag(Ji, Jm), where Jj is the Jordan block corresponding to the eigenvalue X;
Notice that e (kh-s)) = diag(e (kh-o), .... , (kh(kh))), where
kh (kh-s))
(kh -
(q. 1q-
(1kh-o) (2)
kh 8
(kh (k s)
(g. 2]!
Combining with the fact that for any k. L,
bhath
E (((())x((I))
((kh-s) e (1h-s) ds
khath
((kkh-s)pp e (1h-s) ds,
conclude that for any ho S 1, tr {EE (II)))x(II) ]]} is linear combination of Lı,i, and L2 for all i, j, where
/ kh s) (1h- ds
L1.33 = C1,i.
=Cindd edch t (1tt-())))))a)))
do t
bb C2, = C2 (()((tto-))+2 (1b- -)] (k) - 8) (th - s) ds
where Cla.j Ciyy are some constants and q E {0, g 1}. ã E (0,... 96 1}.
For the integral in L2,4.j ai + qj I n 1, we can have the inequality:
(kh 8) (th - 5)d ds
kb S pm- /
e(di(th- ()) ds.
(40)
Since
Ir (x()))(( $1.J1.52J2 KJ l1.2E((1.)
ΣΣ
Liyiish Liggadia
and all the terms are nonnegative. We drop all terms that include C2.5.j factor and only include the C with & = terms in the lower bound of part 1. That is to say, the lower bound of part is m Var.Var(h. A²).
The upper bound of part can be obtained by replacing all f1.a, factors by C2. and use the bound
given in Equation (40). This leads to the upper bound for part is (Ca+Ca(A),-* A. (T) )o oTT2n4s
Bh
O ).
26

---

For Part let g(t) E (x (X) on [0, T). Then [V tion of g(t), by the property of Riemann approximation,
the left Riemann sum approxima-
E
Vrl ~ + VM
where
=r = tr {QE (x) =
e (e-a) ds do).
which is constant depends X1,
Am, T. Thus
VM
C Am, +2
which has the same order as the scalar case finite-horizon undiscounted setting. Thus the result in Equation (35) is obtained by combining part bounds and part 2 approximation.
As we explained in the beginning this proof, in the the similar arguments in the proof of Equation (35) to obtain result Equation (36).
discounted setting, we will follow
For the infinite-horizon discounted setting, the corresponding part in the MSE is the same as the part in MSET of Equation (36). The part is approximated by using the decomposition Equation (12) and the fact that
V1,00 V1,0= - f
(x()) C .mm.
To verify V0 is O()²",, one can find the bounds of Vr, by using the similar arguments in the above proof of Equation (35) and the following inequality:
Lo (loothsee (t (0--)) s)ūc+ās ds
sm LI ((attti(tes))) ds (A: 11)
1n-
(clhtaaje-1) -1
Then the components in " + JT (A,+2,) (e(a+ -) 1) dt and upper bounded by fr. (uttiy) (eld -1 de. By
dt is lower bounded by
r'mn-1
the celebrated approximation of incomplete gamma function when T is large, we have
Jr
r'gn-1 (chittyee1) dt (1++2g) (De (1)+
TT
(chnth)1-1)
Followed by
VT,00 tr ur0off L. 3B (() dt).
can obtain that V0 Cr,, )m))) This result leads the fact that part 2 is
(Ca(A1,"" Am, 7, T) + Co(Ai, ... Am, 7, Th) o 2 + (Cio()i, Am, 7, 2) +Ci1(A1,".. .mm 7, T)h²) o²TT + Cia(Ar, Am. T O(h)),
which coincides with the Var(hA;) in the fiinite-horizon discounted scalar case. The results in then follows.
D Complements to Numerical Simulations
The LQR experiments were run MacBook pro with an i9 CPU and 16GB of RAM.
27

---

D.1 Randomly-sampled Matrices
The matrices A in Figure 1(c) and Figure ((d), corresponding to controlled multi-dimensione linear systems, are generated according to the procedure described below. It ensures the stability of the resulting system, i.e. that eigenvalues of the sampled matrix are negative.
The procedure works by random sampling an eigendecomposition. starts with uniformly sampling Two eigenvalues from disjoint, bounded intervals, A |-1.5, -1.0) and X E (-1.0, -0.75 The final eigenvalue is set to be X2 -1.0. Note that since all the eigenvalues sampled are negative, any matrix whose eigenvalues are λ1 A2, Å3 said to be stable. Next, the eigenvectors are sampled randomly from the classical compact groups detailed in [Mezzadri, 2006]. For that, we randomly sample an orthogonal matrix using built-in SCIPY [Virtanen al., 2020] routine, ORTHO_ BeTHO_GROUP.RY. GROUP.RVS. Now let A diag( A1, A2, As), the random, dense, stable matrix A is obtained by computing the product = AL.
D.2 Trade-off in LQR with Scaled Identity Matrices
In order to better understand the transition from scalar to vector case in the trade-off of the step-size due the MSE in Section 3, numerical experiments for the case of identity matrices scaled by constant are provided in this section. This allows to characterise the role played by the eigenvalues, with respect to the parameter in the scalar case.
T-2, B-4096
T=32, B=16384, y=
10a
10a
109
(hx(h) v)²
104
10.3
10a.
10
A--0250
Am.0251
A--0306
10-1
Amdhh
10-3
A- 26
A- 25
Am-4
A-44%
10-a
10
10
(a) = 3, finite horizon
(b) n2 3, infinite horizon
Figure 4: Mean-squared error trade-off in LQR with scaled identity matrices A. The plots show the dependence of the optimal step-size on the eigenvalues of the linear systems in both finite and infinite horizon settings. The same trend of the scalar case w.r.t. the parameter a can be observed here.
As expected, results in Figure 4 suggest that the trade-off for scaled identity matrices is very similar to the one in the scalar case. In this simple case the eigenvalues that are identical on all dimensions play the same role as the parameter o, i.e., by decreasing them, the trade-off shifts towards smaller value for the optimal step-size, suggested also by Figure ((b).
D.3 Comparison of Empirical and Analytical MSEs in One-dimensional Langevin Systems
Figure compares the empirical MSE in Figures (a) and 1(b) with the analytical MSEs, including both the exact and approximate versions. We can observe that the empirical results are consistent with the analysis. The error in approximate MSE becomes noticeable for large especially when h > 1, as expected. Nevertheless, the optimal h² remains consistent.
D.4 Implementation Details for Nonlinear Systems Experiments
We summarize the environment-specife parameters in Table 1 for the nonlinear-system experiments.
Compute Resources For training the stable policy for non-mujoco environments, we used a server with one GTX 1080. The training for MuloCo environments was conducted on a cluster, using single V100 Volta for each environment. For inference, since we need to run many episodes, we scaled things up cluster of CPUs.
28

---

T=B, a=-1.0
T=8, a=.1.0
10a
10-
(W/(h) -V²
(Wwh)) - Vy2
100
10c
10
10
10-1
B-32263
10301
10
8-12766
E-1004
B--02224
B-45526
10
10
10
100
10
10
10
10
10"
10'
h
(a) exact MSE, vary B
(b) approximate MSE, vary
T=8, B=16384
T=8, B=16384
10a
10a
-0
10-2
(1
10-4
10-4
10.1
10
10
100
20"
10
10
10
10
10"
10'
(c) exact MSE, vary a
(d) approximate MSE, vary
Figure Comparison between the empirical (solid) and analytical MSEs (dashed) in one-dimensional Langevin systems.
Training Details We used the CDAU algorithm described [Tallec et al., 2019] train the policies since we find this algorithm to be robust to time discretization, especially when the environment runs at 0.001. We closely followed the hyper-parameters setup described Section 2 in the Appendix of [Tallee et al., 2019]. For more details, please refer to their paper, and the code in the supplementary materials.
Inference Details We run the policy for 300k episodes at the finest time discretization 5t = 0.001 (600k in InvertedDoubePenddulmm and Pusher) and store the reward sequences. The number of episodes is chosen to be sufficient for 30 runs and the largest possible number of trajectories (depending on and the data budget B). These data get down-sampled offline for different choices of ht. The episodes are randomly shuffled when we vary B.
29

---

Table I: The setup of the environments. In MuJoCo environments in OpenAl Gym, 5l timestep frame_skip skip, where 'timestep" (the step size of the MuJoCo dynamics simulation) and 'frame skip' (the algorithmic step size) are two pre-set quantities in their implementation. In our setup, öt 0.001 seconds for the proxies to the continuous-timg environments.
Environment
Episode Length
Original*
Horizon T
(steps)
8t
(seconds)
Pendulum
200
0.05
10
BipedalWalker
500
0.02
InvereedDoubleeenddulum
1000
0.05
50
Pusher
1000
0.05
Swimmer
1000
0.04
40
Hopper
1000
0.008
HalfCheetah
1000
0.05
50
Ant
1000
0.05
50
Environment
Bo
h
Pendulum
10k
[0.001, 0.002, 0.004, 0.01, 0.02, 0.04, 0.1]
Walker
10k
[0.001, 0.002, 0.004, 0.01, 0.02, 0.04, 0.1]
InverredDDublleeenduuum
25k
[0.002, 0.004,,000,,,002,,,00,, 0.0,, 0.4, 1]
Pusher
25k
[0.002, 0.004, 0.02, 0.1, 0.4, 1]
Swimmer
20h
[0.001, 0.002, 0.004, 0.01, 0.02, 0.0,0.0
0.004, 0.01, 0.02, 00.00
Hopper
8k
0.1]
HalfCheetah
25k
[0.002, 0.004, 0.01, 0.1, 0.4.0.0.22,.00 0.4]
Ant
25k
[0.002, 0.004, 0.01, 0.0.0000002.00001111.0000000000,
30


Reviews:
[{"review_id": "clTjVkmgjT", "reviewer": "Reviewer_hJmD", "summary": "This paper examines the time discretization for continuous value estimation. By analyzing Monte-Carlo value estimation for LQR systems for both finite-horizon and infinite discounted horizon settings, the authors finds that there is a fundamental trade-off between approximation error and statistical error in value estimation, which indicates there is an optimal choice for time discretization that depends on the data budget. The authors also demonstrate the trade-off in numerical simulation of LQR instances and non-linear mujoco environments.\n\n", "questions": "My questions is the weakness point I listed. ", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "\n- The one dimension example presented in the paper is helpful for understanding\n- The experiments in the paper clearly support the theoretical analysis and results.\n", "weaknesses": "- My only concern is the practise of the setting or scenarios: people may argue that the $\\delta t$ is not randomly chosen and might be fixed or determined by the system itself. Can the authors illustrate some realistic scenarios that we can leverage the methods you proposed. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the time reviewing our work and for providing valuable feedback. \n\nWe are motivated by real-world scenarios where one must choose the frequency at which sensors operate to get samples of the system signal. Indeed, in many real-world applications, sensors sample at a higher frequency than necessary, and data is downsampled later on.\n\nA realistic scenario where a practitioner chooses $h$ when evaluating the policy of an in production recommender systems at large streaming companies, such as YouTube or Netflix, where the recommendations are entire homepages on the streaming platform. In this setting, it is infeasible to log every single interaction the system has with each user, due to the massive amount of interactions. The solution adopted in practice is to store only snapshots – subsets – of the latter, i.e. only a fraction of the total interactions and corresponding recommendations are logged. Storing a snapshot is costly, both in memory and in computation, as it interferes with other components of the production pipeline. A high sampling frequency causes real performance issues in the production pipeline and requires a large memory, only to marginally improve the estimated value of the recommender system. This is not desirable if the cost of data outweighs the latter improvement. Our analysis suggests that careful consideration should be taken when setting the snapshot frequency in order to mitigate the adverse effects of having to deal with a cumbersome amount of data.\n\nAnother example is when applying RL to water treatment systems [Chen et al. 2021], one is faced with choosing a proper sampling step-size - or sampling frequency of the sensor. Sensors that gather data at a higher frequency tend to be more expensive. Our result suggests that opting for the faster sensor without careful consideration may not be the most economical or efficient strategy. \nEven in scenarios where $h$ is fixed (e.g. when a sensor is already in place in an older system), our result provides insights into whether data efficiency can be further improved in existing systems. The implications are two-fold. First, our findings can identify potential areas for improvement to guide future system upgrades. Second, if $h$ is smaller than the optimal value suggested by our method (i.e., the operating frequency of the sensor is too high), it is not necessary to store all samples.\nNonetheless, for many sensors used in real-world applications, it is indeed possible to decrease the operating frequency. This insight is particularly useful for edge devices with limited hardware capabilities for storage and computation.\n\nIn broad terms, our analysis seeks to understand the associated benefits and costs – with the constraint being a fixed data budget – when downsampling a system. \n\n**Reference:**\n\nChen, K., Wang, H., Valverde-Perez, B., Zhai, S., Vezzaro, L., Wang, A.  (2021).  _Optimal control towards sustainable wastewater treatment plants based on multi-agent reinforcement learning._  Chemosphere, Volume 279, 130498."}, {"review_id": "pzjb5ldJfN", "reviewer": "Reviewer_cepd", "summary": "The paper studies the optimal temporal discretization level to achieve the best Mean Square Error (MSE) in continuous value estimation, considering a fixed budget constraint (number of total Monte-Carlo samples). The paper provides theoretical analysis on a 1-dimensional Langevin dynamical system with quadratic costs and derives the asymptotic optimal step-size under both finite and infinite horizon settings. Extensive numerical studies, including non-linear MuJoCo environments, support the theoretical findings and reveal the bias-variance tradeoff associated with the choice of temporal discretization level.", "questions": "Suggestions:\n1. If simplicity is not our primary criterion, it would be interesting to explore alternative discretization plans beyond uniform discretization.", "limitations": "n/a", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Motivation and clarity:\n- The paper presents a clear motivation and an interesting problem setup regarding temporal resolution in continuous value estimation.\n- The paper is well-written with a clear structure. Key messages, such as the problem setup, objectives, key theoretical results, and numerical result figures, are easily understandable.\n\nQuality of the paper:\n- Section 3 delves deep into a special case of a 1-dimensional Langevin Process, fully characterizing the MSE and providing insights into the optimal step-size.\n- Section 4 builds upon the results from Section 3 and provides extensive numerical studies in various environments.\n- The conclusion of the paper effectively demonstrates the limitations and shows a deep understanding of the topic, as well as potential avenues for future research.", "weaknesses": "Limitation of the scientific impact:\n- My major concern lies in the limitation of the impact, as also mentioned in the paper's conclusion. The optimal resolution results are constrained to Naive Monte-Carlo estimation, which typically serves as a baseline for policy evaluation algorithms and cannot be directly extended to advanced methods such as temporal difference.\n- Although the numerical results demonstrate the bias-variance tradeoff for non-linear systems, the current theoretical results on the 1-dimensional linear dynamical system cannot be directly extended to more complex systems, where exact characterization no longer exists.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the time reviewing our work and for providing valuable feedback.  \n\nOne clarification we would like to respectfully add is that tight bounds for the general case of a linear $n$-dimensional system are established in the paper. That is, the theoretical results are not restricted to the $1$-dimensional case.\n\n### Monte-Carlo estimation\nWhile focusing on the case of Monte-Carlo estimation, the analysis serves as an essential starting point for studying the fundamental problem of step-size selection, which has been largely overlooked in the literature and there are currently few works that address this issue - as corroborated by two other reviewers. Historically, the Monte Carlo method has been instrumental in developing other reinforcement learning (RL) algorithms, such as Temporal Difference learning.\\\nWe agree that this line of research can be further explored by considering different estimators (e.g. system identification case - pointed out by another reviewer - or Temporal Difference estimation) and/or different sampling schemes (e.g. adaptive step-size). In particular, the Temporal Difference estimator has a sufficiently simple form that appears to admit tractable analysis. We are indeed exploring similar analyses for TD and other algorithms as part of our future work. \n\n### Alternative discretization plans beyond uniform discretization\nIt is indeed interesting to consider non-uniform discretization schemes, such as through an adaptive sampling scheme, similar to those adopted in solving SDEs [Ilie et al. 2015]. We view this paper as providing the necessary first steps to providing a basis for evaluating alternative discretization schemes.\\\nFrom a theoretical perspective, a non-uniform step-size creates additional issues, since the number of steps in each trajectory might vary. A deeper investigation of adaptive step-size schemes represents an interesting future direction.\n\n### Theoretical results for more complex systems\nIt is true that the detailed analysis given in the paper requires the exact solution of the stochastic differential equation, which is unavailable for most nonlinear systems. However, one can leverage the tight bounds established for an $n$-dimensional linear system and expand the dimensionality in order to approximate more complex nonlinear dynamics in many cases.\\\nThis approximation would then exhibit the same trade-off.\n\nWe believe that these findings already make a valuable contribution to the field. That said, we agree with the value of further exploration in more complex settings. We thank the reviewer for pointing out these other potential research directions.\n\n**Reference:**\n\nIlie, S., Jackson, K. R., & Enright, W. H. (2015). *Adaptive time-stepping for the strong numerical solution of stochastic differential equations.* Numerical Algorithms, 68(4), 791-812."}, {"review_id": "3nJMKugHZA", "reviewer": "Reviewer_37Kf", "summary": "The authors study the impact of time discretization on RL methods in order to improve data efficiency and show that that data efficiency can be significantly improved by leveraging a precise understanding of the trade-off between approximation error and statistical estimation error in value estimation. They conduct a theoretical analysis followed by numerical ones on MuJoCo environments to demonstrate value. ", "questions": "No specific questions. All concerns are addressed in the paper+supplementary materials. ", "limitations": "Authors have done a good job in stating the limitations that I agree with- (a) it would be interesting to see how this work extends to more advanced techniques that MC estimation, like TD learning. (b) Secondly, studying the full control setting that includes policy optimization and, (c) simplifying assumptions like linear models with additive noise are considered, but in real world these assumptions don't hold where the observations are noisy, and systems are non-linear. So how this analysis extends to real world sample efficiency for RL algorithms is unclear from the work. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Quality and Clarity: The paper is well written and presents a clear and detailed theoretical framework to study the effect of time discretization in terms of data efficiency for control problems. The derivations are easy to follow with necessary background provided in the supplementary materials. \n\nOriginality: Marginal improvements are demonstrated by providing the necessary theoretical foundation which is missing from some prior work like Lutter et al as pointed out by the authors. \n\nSignificance: The paper addresses an important and relevant problem of improving data efficiency for data hungry RL algorithms. \n", "weaknesses": "Sample efficiency is a huge pain point for solving control tasks in real world where collecting large amounts of data is costly, infeasible or even dangerous. A key weakness I found is the fidelity of this approach in real world scenario. I found the theory to be sound, but built on a lot of simplifying assumptions that do not hold true in real world. So although the work is interesting, I am not sure how strong will these results hold on real world data where the noise isn't additive, or the model isn't linear. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the time reviewing our work and for providing valuable feedback.\n\nWhile it is true that the technical analysis holds only in the case of linear dynamics, we explicitly conducted experiments in nonlinear systems to understand if the theoretical findings could still hold when certain assumptions were not met. Note indeed that in the non-linear Mujoco environments, the setting is significantly different from the one considered in the exact analysis. Nonetheless, the general results seem to extend quite remarkably to this more challenging scenario. This suggests that the results may have broader applicability than the specific conditions under which the theoretical analysis was established. \\\nMany nonlinear behaviors can be approximated by a high-dimensional linear system, which would nevertheless be bounded by our most general results on $n$-dimensional systems, hinting at the fact that similar trade-offs could characterize nonlinear systems as well, as demonstrated through numerical analysis.\n\nWe believe that this work broadens the perspective and provides valuable opportunities for further exploration and development."}, {"review_id": "IR8m97avYm", "reviewer": "Reviewer_uBm7", "summary": "For the reinforcement learning (RL) setting, many problems are cast into a fixed discrete time sampling of the true underlying system. This paper investigates given some fixed data budget available, what is the optimal sampling rate in terms of temporal resolution to balance the trade-off between approximation and statistical estimation error. Theoretical results are obtained for the exact form of these errors is derived for the MSE of a Monte Carlo in a Langevin process for both finite and infinite horizon setting. This shows that there is an optimal choice in temporal resolution to balance these errors, and this is verified by simulated linear quadratic systems. Similar kind of trade-offs can be found in empirical (nonlinear) environments from gym and MuJoCo.", "questions": "How might an adaptive sampling procedure affect the results?\n\nIt is assumed that the estimation horizon is the same length as the episode, this seems like a strong assumption which does not hold in a lot of applications (i.e. you do not know how long the episode is a priori, nor are the episodes the same lengths). How would the results in finite horizon change in this case?\n\nShould the $h$ on line 165 be $h^*$?\n\nCan you clarify where the MSE_T between line 168 and 169 come from?\n\nThe second term on the right hand side for the MSE_T has denominator $hB$, will this assume $h = \\mathcal{O}(B^{-1/3})$ therefore the second term is $\\mathcal{O}(B^{-2/3})$ hence till tends to 0?", "limitations": "The theoretical results obtained seems to assume a fixed observation/estimation horizon T, that is pre-set, but since episode are not of fixed lengths in RL settings, and indeed may increase as the policy improves, this may affect the validity of the theoretical results.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a well-written paper which looks at a problem in value estimation that does not appear to have been explicitly studied on this level before. There is detailed theoretical analysis for the case of a Langevin process, and the results are interpreted in a practical way. The demonstration of these theoretical results in numerical simulations in Section 4.1 is very clear. Verification of similar effects on empirical environments is useful to see.\n\nOverall, this paper contributes to the literature on additional considerations that should be made in continuous time RL setting, and it would be useful for future developments in this area.", "weaknesses": "Practically the policy is varying at the same time, and perhaps the same step size should not be used over the course of training. Therefore it may be that the practical impact on implementation of this paper may be limited.\n\nFor Figure 3, it seems to be misleading to fit a line matching $h = \\mathcal{O}(B^{-1/3})$ for the empirical experiments. Particularly given lines like for that of the InvertedDoublePendulum, clearly a different gradient should be considered. The observation on these empirical experiments are interesting, but there is no need to force the results on these nonlinear systems to match the analysis in the previous section.\n\nIn setting the step-size $h$, this relies on the ability to perform experiments on a smaller data budget first, which may not always be possible in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the time reviewing our work and for providing valuable feedback. We will correct the typos pointed out by the reviewer. In the following, we address the main concerns.\n\n> Can you clarify where the $\\text{MSE}_T$ between line $168$ and $169$ come from?\n\n`Re:` It was obtained by plugging $h^*$ from Eq. ($9$) into the $\\text{MSE}_T$ in corollary $3.2$.\n\n> The second term on the right hand side for the $\\text{MSE}_T$ has denominator $hb$, will this assume $h = \\mathcal{O}(B^{-1/3})$ therefore the second term is $\\mathcal{O}(B^{-2/3})$ hence till tends to $0$?\n\n`Re:` Note that the expression for the optimal $h$ is indeed $\\mathcal{O}(B^{-1/3})$, therefore the conclusion holds. The optimal $\\text{MSE}_T$ tends to $0$ as $B\\to\\infty$. The intuition is that given unlimited data ($B\\to\\infty$) and finite horizon $T$, the approximation error and variance both reduce to $0$ due to $h\\to0$ and having infinitely many episodes.\n\n> Figure $3$\n\n`Re:` Figure $3$ was meant to illustrate the comparison between a line fitted on data with a fixed order in $B$, given by the theoretical analysis, and experimental data points. We did not intend to force the results: InvertedDoublePendulum was indeed a negative example. The provided chart was indeed meant to show that the approximation given by the knowledge of the order in $B$ is good, but not always accurate. We will state it more clearly in further revisions to improve clarity.\n\n> \"estimation horizon is the same length as the episode\"\n\n`Re:` Perhaps we misunderstand the reviewer’s point: we explicitly analyzed the discounted infinite horizon case where the estimation horizon $T$ is necessarily different from the system horizon $\\tau$, and so we did not assume the estimation horizon is the same length as the episode.\n\n### Non-uniform horizon\nThis is an interesting issue. We first note that the technical analysis is grounded in LQR systems, where the conventional setting involves a fixed episode horizon, either finite or infinite (with discounting), without considering early termination.\\\nIn the nonlinear experiments, we utilized the benchmark Mujoco environments, which have a fixed time limit. Coupled with our assumption of a stable policy, this ensures that all episodes maintain consistent lengths. Hence a uniform horizon aligns well with the scope of our work in both the theoretical analysis and experimental results.\\\nWhile we acknowledge the potential interest in extending our analysis to scenarios with non-uniform horizons, this would necessitate a different formulation, potentially adopting the approach proposed in [Poiani et.al 2023]. We would like to explore this direction in future work.\n\n### Adaptive sampling\nAn adaptive sampling procedure, similar to those adopted in solving SDEs [Ilie et. al. 2015], could represent an interesting direction for future work. Nonetheless, there are few factors that complicate its applicability in the current setting.\\\nFrom a practical perspective, the most important difficulty lies in the additional hyperparameters, which needs to be fine-tuned.\\\nWith regard to the analysis, establishing a theoretical framework for investigating non-uniform step-size is not straightforward, as it involves additional degrees of freedom, due to the fact that the number of steps in each trajectory does not need to be consistent, thus making the optimal step-sizes under such a setting not necessarily unique.\n\n**References:**\n\nPoiani, R., Metelli, A. M., & Restelli, M. (2023). *Truncating Trajectories in Monte Carlo Reinforcement Learning.* arXiv preprint arXiv:2305.04361.\n\nIlie, S., Jackson, K. R., & Enright, W. H. (2015). *Adaptive time-stepping for the strong numerical solution of stochastic differential equations.* Numerical Algorithms, 68(4), 791-812."}, {"review_id": "7J4rpRaDxu", "reviewer": "Reviewer_sR6e", "summary": "The paper discusses the impact of time discretization on estimating cost functions for continuous-time stochastic optimal control problems. The authors consider a discrete-time Monte Carlo estimator based on the left-rule formula for numerical integration. Under the LQG assumption, the authors derive closed-form results for the mean square error (MSE), which depend on the sample size and the integration step size. The authors provide a numerical evaluation based on their modeling assumptions and propose hypotheses on how to extend their findings to general nonlinear systems.", "questions": "-", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "A large class of problems is naturally described as continuous-time systems, making investigations on this topic important. The paper effectively demonstrates how time discretization impacts the estimation of continuous-time quantities, such as the cost function. The work is well written and easy to follow. The results derived in this work are well presented and properly justified.", "weaknesses": "I believe the main weakness lies in the significance of the contribution itself. It is to me not particularly surprising that closed-form results for MSE under the LQG assumption can be found. Additionally, it is unclear to me when this method should be used. For instance, if one knows they have an LQG problem, they already know that the value function is a quadratic function and its coefficient can be computed by estimating the dynamics parameter.\n\nFurthermore, the numerical evaluation for the nonlinear systems appears somewhat weak, and I am not sure whether the results can be easily transferred from the linear to the nonlinear regime.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the time reviewing our work and for providing valuable feedback.\n\nWe respectfully note that the formulation of MSE under a fixed data budget has not been explored before. While it may be reasonable to anticipate a closed-form MSE under this formulation, we believe that the process of devising this formulation and developing an exact characterization of the trade-off w.r.t. the step-size constitutes a significant contribution, even if it appears intuitive in retrospect.\\\nNote also that the aim of the paper is not to provide a method for estimating the value-function in the LQG setting, but rather to characterize an overlooked phenomenon affecting any continuous stochastic system.\n\nOur experiments on nonlinear systems in standard benchmark extend beyond the typical scope of experiments in LQG literature. These were designed to assess how well the theoretical findings could still hold when certain assumptions were not met. Interestingly enough, the results seem to extend quite remarkably to this more challenging scenario. This suggests that our findings may have broader applicability than the specific conditions under which our theoretical analysis was established.\\\nWe hope that this clarifies the purpose and the scope of the evaluation for nonlinear systems, in response to the comment that it “appears somewhat weak”. If it does not address your concern, we kindly invite you to provide further clarification."}]

Author rebuttal:

Meta-review: This paper provides a precise characterization of the approximation, estimation, and truncation errors incurred by Monte-Carlo policy evaluation in continuous-time linear stochastic dynamical systems with quadratic cost. While the setting is well-known, the analysis reveals the fundamental bias-variance trade-off, which is new. All the reviewers reached the consensus that the paper should be accepted. I recommend the paper be accepted. However, the authors should incorporate the suggestions from the reviewers as promised.
Decision: Accept (poster)