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: Submitted to ICLR 2023 (2023)
Keywords: Temporal Discretization
Continuous Time
Langevin System
LQR
Policy Evaluation

Abstract: A default assumption in reinforcement learning and optimal control is that experience arrives at discrete time points on a fixed clock cycle. Many applications, however, involve continuous systems where the time discretization is not fixed but instead can be managed by a learning algorithm. By analyzing Monte-Carlo value estimation for LQR systems in both finite-horizon and infinite-horizon settings, we uncover a fundamental trade-off between approximation and statistical error in value estimation. Importantly, these two errors behave differently with respect to time discretization, which implies that there is an optimal choice for the temporal resolution that depends on the data budget. These findings show how adapting the temporal resolution can provably improve value estimation quality in LQR systems from finite data. Empirically, we demonstrate the trade-off in numerical simulations of LQR instances and several non-linear environments.

Under review as a conference paper at ICLR 2023
MANAGING TEMPORAL RESOLUTION IN CONTINUOUS VALUE ESTIMATION: A FUNDAMENTAL TRADE-OFF
Anonymous authors Paper under double-blind review
ABSTRACT
A default assumption in reinforcement learning and optimal control is that expe- rience arrives at discrete time points on fixed clock cycle. Many applications, however, involve continuous systems where the time discretization is not fixed but instead can be managed by learning algorithm. By analyzing Monte-Carte value estimation for LQR systems both finite-horizon and infinie-hhrriag settings, we uncover fundamental trade-off between approximation and statistical error in value estimation. Importantly, these two errors behave differently with respect time discretization, which implies that there is optimal choice for the tempo- ral resolution that depends on the data budget. These findings show how adapting the temporal resolution can provably improve value estimation quality in LQR systems from finite data. Empirically, we demonstrate the trade-off in numerical simulations of LQR instances and several non-linear environments.
INTRODUCTION
In many real-world applications of control and reinforcement learning, the underlying system evolves continuously in time. For instance, physical system such robot is naturally modeled as a stochastic dynamical system. In practice, however, sensor measurements are usually captured discrete time intervals, and the practitioner must make decision about how to discretize the time dimension, i.e. choosing sampling frequency or a measurement step-size. A common belief is that a finer time discretization always leads better estimation of the system properties and the control cost or the reward in reinforcement learning. As we show, this is only true with an unlimited data budget. In practice there are always limitations on how much data can be collected, stored and pro- cessed. Consider for example the task of episodic policy evaluation with finite data budget. A higher temporal resolution means that more data is collected within fewhir episodes. This inevitably leads to the question on how to optimally choose the time discretization for the task at hand.
The practitioner therefore faces a fundamental trade-off: using a finer temporal resolution leads to better approximation of the continuous-time system from discrete measurements, but the conse- quence of collecting denser data along fewer trajectories leads to larger estimation variance with respect to stochasticity in the system. This indeed true for any system with stochastic dynam- ies, even if the learner has access to exact (noiseless) measurements of the system's 's state. In this paper, we show that data efficiency can be significantly improved by leveraging a precise under- standing of the trade-off between approximation error and statistical estimation error in long term value estimation - two factors that react differently to the level of temporal discretization.
The main contributions of this work are twofold. First, we consider the simplest and canonical case of Monte-Cane value estimation by Wiener process) with quadratic instantaneous costs. Although the setup is specialized, it is simple enough such that we can obtain analytical expressions of the least-squares error that exactly characterize the paprooiiatiionesttmaaiii we present a numerical study that illustrates and confirms the trade-off both linear and non-lined systems, including several MuJoCo control environments. Our findings imply that practitioners should pay attention to carefully choosing the step-size parameter of the estimation to obtain the most accurate results possible.
Langevin dynamical system (linear dynamics perturbed
trade-off with respect to the step-size parameter. Second,

---

Under review as a conference paper at ICLR 2023
1.1 RELATED WORK
There is sizable literature on reinforcement learning in continuous-time systems (e.g. Doya, 2000; Lee & Sutton, 2021; Lewis et al., 2012; Bahl et al., 2020; Kim et al., 2021; Yildiz et al., 2021). I). These previous works have largely focused on deterministic dynamics, and do not investigate trade- offs in temporal discretization. A smaller body of work has considered learning continuous-time control under stochastic (Baird, 1994; Bradtke & Duff, 1994; Munos & Bourgine, 1997; Munos, 2006), or bounded (Lutter et al., 2021) perturbations, but with a focus on making standard learning methods more robust small time scales (Tallec al., 2019), again without explicitly managing the temporal discretization level. There have also been works that characterize the effects of temporal truncation infinite horizon problems (Jiang et al., 2016; Droge & Egerstedt, 2011). Despite these prevailing topics in the literature, we find that managing temporal discretization offers substantial improvements not captured by these previous studies.
The LQR setting is standard framework in control theory and it gives rise to fundamental op- timal control problem (Lindquist, 1990), which has proven itself to be a challenging scenario for Reinforcement Learning algorithms (Tu & Recht, 2019; Krauth et al., 2019). The stochastic LQR considers linear systems driven by additive Gaussian noise with quadratic form for the cost, which is sought to be minimised by means of a feedback controller. Although it is well-understood scenario and a closed form of the optimal controller is known thanks to the separation principle (Georgiou & Lindquist, 2013), only recently the statistical properties of the long-tenm cost have been investigated (Bijl et al., 2016). The work in this paper also closely related to the now siz- able literature reinforcement learning in LQR systems (Bradtke, 1992; Krauth et al., 2019; Tu & Recht, 2018; Dean et al., 2020; Tu & Recht, 2019; Dean et al., 2018; Fazel et al., 2018; Gu et al., 2016). These existing works uniformly focused on the discrete time setting, although the benefits of managing spatial rather than temporal discretization has been considered (Sinclair et al., 2019; Cao & Krishnamurthy, 2020). Wang et al. (2020) studied the continuous- LQR setting but it focused on the exploration problem rather than the temporal discretization.
There is compelling empirical evidence that managing temporal resolution, typically via action per- sistence (Lakshminarayannn et al., 2017; Sharma et al., 2017; Huang et al., 2019; Huang & Zhu, 2020; Dabney et al., 2021; I; Park et al., 2021), can greatly improve learning performance. Even grid worlds (Sutton & Barto, 2018) can be seen leveraging form of action persistence, where a coarse spatial discretization is imposed on an otherwise continuous two dimensional navigation problem to improve learning efficiency. These empirical findings have recently been supported by an initial the- oretical analysis (Metelli et al., 2020) that shows temporal discretization plays a role in determining the effectiveness of fitted Q-iteration. The analysis by Metelli et al. (2020) does not consider fully continuous systems, but rather remains anchored in a base level discretization and only provides worst-case upper bounds that do not necessarily capture the detailed trade-off's one faces in practice.
Choosing the temporal resolution can also be understood as a non-linear experimental design prob- lem (Chaloner & Verdinelli, 1995; Ford et al., 1989). By choosing the time discretization, the exper- imenter determines how to allocate measurements for a given data budget. What is peculiar to our objective is that any fixed design has a constant approximation error (bias) that persists even when the number of data points becomes infinite. At the same time, the bias can also be managed by scar- ifying estimation error (variance). Optimal designs that consider the bias-variance trade-off jointly have been studied previously (e.g. Bardow, 2008; Mutny et al., 2020; Mutný & Krause, 2022).
2 POLICY EVALUATION IN CONTINUOUS LINEAR QUADRATIC SYSTEMS
In the classical continuous-time linear quadratic regulator (L.QR), a state variable X(t) E TR. evolvves over time & 2 0 according to the following equation:
dx (f) (t) dt + (U) dt (t).
(1)
The dynamical model is fully specified by the matrices A E TRax B E Rexp and the diffusion coefficient a. The control input is U (-) E 12 is given by a fixed policy, and W(t) is a Wiener process. The state variable X Xf) is fully observed. For simplicity, we assume that the dynamics start at X (0) 0 E RDn (c.f. Abbasi- Yadkori & Szepesvári, 2011; Dean et al., 2020).
2

---

Under review as a conference paper at ICLR 2023
The expected quadratic cost J is defined for positive semi-definte, symmetric matrices Q R and R E RPxp, a system horizon T S oo and a discount factor y E (0, 1]:
J, J.=/. x (x (t) +
(t) RU (t)
(2)
In the following we consider the class of controllers given by static feedback of the state, i.e.;
( KX (t)
where K I2x=" is the static control matrix yielding the control input. It is well known that in infinite horizon systems with discounting, the optimal control is the form Eq. (3). The specific choice of policy plays particular role in what follows, therefore
reduce the LQR in Eq. (1)
further to a linear stochastic dynamical system described by a Langevin equation. Using the defini- tions A A + BK and Q more compact form:
K RK, express both the state dynamics and the cost in
J, I.-..-0 (t) QX (t) dt
d - AX (t) + (t)
(4)
The expected cost V, is the expectation the cost w.r.t. the Wiener process, V, [
Equation (4) is what analyze in the following. From on, explicitly distinguish the finite- horizon setting where т < 0C, S 1 and the cost is V,, and the infinitehhorizon setting where 00, 7
and the cost is Vo
Monte-Carlo Policy Evaluation Our main objective of policy evaluation is to estimate the ex- pected cost from discrete-time observations. To this end, choose uniform discretization of the interval [0, 7) with increment h resulting in N W= -T// time points 4 == kh for & E {0, 1,..., .N-- Here, the estimation horizon T, such that T oo and 7' т, is chosen by the practitioner (for sim- plicity assume that T/h is an integer). With the N points sampled from one trajectory, a standard way to approximate the integral in Eq. (4) is with the Riemann sum estimator
N-1
j (h) = Σ 7 (4x) (t+)
(5)
k=
To estimate Vr, we average independent trajectories with cost estimates J,,... obtain the MonteeCarlld estimator:
M (
M N
1 Σ M
Our main objective is to understand the mean-squared error of the Monte-Carlo estimator for a fixed system (specified by A, and Q), with the goal inform optimal choice of the step-size VM (h)
Σ
Σ
y fx (tx) Q (tx)
(6)
M
i=1
i=1 k=0
parameter h for a fixed data budget B = M N.
Note that one degree of freedom remains in choosing M and N. For simplicity, require that in the finite-horizon setting, the estimation grid is chosen to cover the full episode [0, 7] which leads to the constraint T 7 N h. We write the least-squares error-surface
function of h and B:
MSE (h, B) = (VVss V
In the infinite horizon setting, i.e. so, the estimation horizon T a free variable chosen by the
experimenter that determines the number of trajectories through M = B
Bh The mean-squared
N
error for the infinite horizon setting is given as a function of h, B, and 7':
MSE (h, B, T) = B[(Vs (h) Voo
(8)
3 CHARACTERIZING THE
ERROR
In the following our goal is to characterize the least least-squares error of the Monte-Carle estimator as a function of the step size h and the total data budget B (and the estimation horizon T in the infinite horizon setting). Our results uncover a fundamental trade-off for choosing an optimal step size that leads to minimal least-squares emoo.
3

---

Under review as a conference paper at ICLR 2023
One-Dimensional Langevin Process To simplify the exposition while preserving the main ideas, we will first present the results for the I-dimensional case. The analysis for the vector case exhibits the same quantitative behavior but is significantly more involved. To distinguish the 1-dimensional from the d-dimensional setting described in Eq. (4), we use lower-case symbols. Let sr(1) E IR be the scalar state variable that evolves according to following the Langevin equation:
dz(t) (t)tt) + adw(t).
(9)
Here, a R is the drift coefficient and v=(() a Wiener process with scale parameter > We assume that S 0, i.c the system is stable (or marginally stable).
The realized sample path episode = I,...,M M is zz(() (with starting state z<0) = 0) and t E [0, []. The expected cost is
V, - f >/9
=
(10)
where r,(1) = qz)(()² is the quadratic cost function for a fixed > 0. The Riemann sum that approximates the cost realized in episode i E [M]] becomes (h) _k=o from M episodes, the Monte-Carlo estimator is (h) = M ΣM J.(h). Since the square of the cost parameter q² factors out of the mean-squared error in Eq. (10), we set q = what follows.
N-1 (kh). Given data
3.1 FINITE-HORIZON
Recall that in the finite-horizon setting we set the system horizon and estimation horizon T to be the same. This implies that the estimation grid covers the full episode, i.c. ANN = '" = т. Perhaps surprisingly, the mean-squared error of the Riemann estimator for the Langevin system (9) can be computed in closed form. The result takes its simplest form in the finite-horizon, undiscounted setting where y and oc. This result is summarized in the next theorem.
Theorem 1 (Finite-horizon, undiscounted MSE). In the finite-horizon undiscounted setting, the mean-squared error of the Monte-Carlo estimator is
Ea T.a)
MSEr(h, B) E1 (h, T,a)
B
where
E1 Ei,,TTaa) 0t (-2ah + 2aah - 1)² (62aT 1)2
16a (e2ah -1)²
TT(,,Taa)= oTT 1 (620T - 1) (4e 2aT 1) (c2ah - 1) (E2nh - 26 1) T
2n (c2ah 1)²
The proof involves computing the closed-form expressions for the second and forth moments of the random trajectories (f) and is provided in Appendices B and C.I. While perhaps daunting first sight, the beauty of the result is that exactly characterizes the error surface as a function the step size h and the budget B.
In principle, for any fixed B, we can optimize to minimize the mean-squared error by searching over possible step-sizes hm T /m for m 1,..., . B. provided knowledge of the system parame- ters a, a and fixed horizon T' On the other hand, the practical scope of this procedure is somewhat limited. On the upside, we show next, the underlying trade-offs can be characterized and under- stood closely in several different regimes. In Section 4, we show through numerical experiments how these insights translate into simulations of linear and non-linear systems.
In the case of marginal stability (a = 0), simpler form of the MSE emerges that is easier to interpret. Taking the limit a - 0 of the previous expression gives the following result:
Corollary (MSE for marginally stable system). Assume a marginally stable system, 0. Then the mean-squared error of the Monte- Monte-Carlo estimator is
TTT2
ATO
1
0 2 (-22 2hT h?2)
MSE B) =
2
4
3
hB
3B
4

---

Under review as a conference paper at ICLR 2023
The first part of the expression can be understood Riemann sum approximation error that is controlled by the ht² term. The second part corresponds to the variance term that decreases with the number of episodes large B. For a fixed data budget B, the step size h can be chosen to balance these two terms (up to lower order terms in 1 1/B):
57 BR The remaining terms are of lower order terms for small h and
2 1/3
h² (B) arg min MSE A>0
(11)
3B
From this, we can compute the optimal number of episodes M Rd Bh that under the assumption B >> 1. we also obtain that M > This is in agreement with the implicit requirement that h is big enough to consider at least one whole trajectory, i.e. h > T/B. Consequently, the mean-squared error for the optimal choice of h (up to lower order terms in 1/B):
1/3 B2/3, We remark
MSEr(h" B) = 3 (3/2) A 2/3
In other words, the optimal error rate as a function of the data budget is O(B-2/3)
We can further obtain a similar form for h* for the general case where a S 0.
Corollary 2 (Optimal step size). For B > 1, the optimal step-size (up to lower order terms in 1/B)
(BB)) (- [4 - eaT + EeT (8aT 4) +5]
1/3
B B-1/3
(2 - 1)2
Moreover, MSE (h", B) & ((33333)
The proof is provided in Appendix C.2 where we also include a more precise expression of h".
Discounted Cost Adding discounting (y 1) in the finite-horizon setting does not fundamentally change the results but makes it more involved (details shown in Appendix C.3).
Vector Case Also for the vector case (n 1) it is possible to exactly characterise the mean- squared error of the Monte-Carlo estimator for the Langevin system in Eq. (9). The closed-form computations will however require to assume that the matrix governing the behaviour of the system is diagonalisable, and stable. The latter is rather mild assumption, as it is sufficient for the system in Eq. (1) to be controllable to ensure satisfiability of this condition. Controllability in fact translates into the possibility of freely adjusting the eigenvalues of the closed-loop matrix A through the choice of the controller K. This means that it is always possible to choose eigenvalues be distinct from each other, so that A is diagonalisable. The explicit form of the mean-squared error, although actually computable, is given by a long formula which is not easy to interpret, and is therefore deferred to Appendix D. The following theorem summarizes the result for the vector case in the form of a Taylor expansion for small h and large B.
Theorem 2 (Mean-squared error vector case). Assume A is diagonalisable, with eigenvalues A An- The mean-squared error of the Monte-Carlo estimator in the finite-horizon, undis- counted setting, is
MSET (h, B) = Fy (h, T,,.,, F2 (h,, T, T,A,,..., An)
(12)
B
where
E1 (h, T,h... )
(C1 101+Ch (.. AT 20h3)
(13)
Es (h, T. A 2p) = (Tz + C2 (M...... An)
T
+0
(14)
B
hB
The proof with the exact derivation of the constants C1, C1 (AI...,,AA)) T2. C2 (AI...., An) can be found in Appendix D.I. Note that the terms composing the MSE are very similar to the ones ob- tained in the scalar analysis. Indeed by comparing them with the expressions in Eq. (28) and Eq. (29)
An),
5

---

Under review as a conference paper at ICLR 2023
(in Appendix C.2), the expression has the same order for h, B and T. The only difference is that in the vector case, cumbersome case the result can more easily be expressed in terms of the system parameter a.
senvalue-depeneen constants are involved, whereas in the scalar
Since the optimal choice for is given by balancing the trade-off between the two terms above, Ej for the approximation error and Eg for the variance term, its expression is analogous to the scalar case, as shown by the following corollary.
Corollary 3 (Optimal step size vector case). Under the assumption that B > 1, the optimal step-size for the vector case is given by
C. C (A A,) h" h²))== (B) = (E,
1/3
C2 (A1, (E,(
TB-1/3 + (BB-1/8) (15)
(,))...;,,))(T)))
The constants in Corollary are clearly the same as in Theorem 2.
General bounds that hold for the case of vector Langevin process with stable matrix A are provided in Appendix D.3. These results show that the mean-squared eπror lies in between two ex- pressions with the same order in h and B, whose difference depends only on T, and the eigenvalues of the matrix. Both the lower and upper bounds are convex functions of h, narrowing down the be- haviour of the step size in this general case. In particular, the lower bound can always be expressed in terms of the mean- squardd error for the scalar case, emphasizing the importance of examining this special case. Although the convex behaviour only proven for the case of a Langevin system, our experimental results (Section 4) exhibit a similar trade-off for general nonlinear stochastic systems.
From the present analysis, it is possible derive guidelines on how set the step-size even for the case of nonlinear and unknown dynamics. Although the sharp order in B for the optimal step-size holds for the case of linear dynamics only, we empirically show in Section 4 that a similar trade-off carries on nonlinear dynamics, and h B-133 is solid choice for the more general setting. While the constant depends on the controlled dynamics (therefore on both the free dynamics and the policy), could be estimated with small budget, in order properly scale the value of for large-scale experiment. This approach does not require the knowledge of the dynamics beforehand, nonetheless it provides systematic way of setting the step size h for any given scenario.
3.2 INFIIITE-HRRION SETTING
The main characteristic of the estimation error. Recall that the -oanite-horizon setting (r oc), the estimation horizon T < oo becomes free variable that is chosen by the experimenter to define the measurement range [0, 7]. Consequently the mean-squared error of the Monte-Carlo estimator suffers an additional truncation error from using finite Riemann sum with N T/h terms approximation to the infinite integral that defines the cost Vas.
setting is the trade-off between approximation and
More precisely, we decompose the expected cost Vo = Vi + Vir where V/ Jo= (t)(x as before, and
Vr = J, >'E[=2()) dt 027T
2aT
(16)
2a
log (7)
log (?) + 2a
The integral is direct calculation based on Lemma becomes
in Appendix B. Thus the mean-squared error
MSE B,T) = EE (VM) - v) = MSE, B) - 2E [vr(h)) - Vir Vr,00 + Vi.oe
(17)
is the mean-squared error of discounted finite-horizon setting. Note that the term V2.200 is neither controlled by a small step-size h nor by large data budget B, hence results in the truncation error from finite estimation. Fortunately, the geometric discounting ensures that Vi2 the tail of the geometric integral. In particular, setting T e >> 1 suffices to ensure that the truncation error is below the estimation variance.
where MSEr(h, B) = (h) - v=)"]
2(?2T', which is not unexpected given that the term constitutes
log(B)/ (o//log(///) for large enough
We summarize the result in the next theorem.

---

Under review as a conference paper at ICLR 2023
Theorem 3 Lifinite-horizon discounted MSE). In the infinite horiize- discounted setting, the squared enror of the Monte-Carlo estimator is
MSE
hB + 144 11 +0(1))++0(0
(18)
where we les C(a,7) (og/7)[a+lo(())) (2atoooo))( and assume that 7" = =
It follows that the optimal choice for the step is h² (B,T) (36T C(a, B) 7
1/5 BB)//, The minimal
least-squares error is MSE (h", T. B) s (
Lastly, we remark that if 7 is treated constant, the cross term E Vas (h) V/r Vr, in Eq. (17) introduces dependence of order (Iry2) ) to the mean-squared error. In this case, the overall trade- off becomes MSE (h, T) (1) (1T+h))) and the optimal step-size h B-1/2,
Vector Case As before, the mean-squared error for the vector can be explicitly computed in closed-form assuming that is diagonalizable. The result reflects the same behaviour as in the scalar case. Conveniently, the MSE in Theorem 3 has been expressed with sharp terms in and B, while confining the dependence on the system parameter a within the constant C, and the impact of higher-order terms in T within Vri This allows us state the same result for the vector case, in which the constant will now depend on the eigenvalues of the matrix A, as well as the discount factor r. These are provided in full detail Appendix D.2.
Corollary 4. For A diagonalisable, with eigenvalues given by Ai...., An. the mean- aaan--quared error of the Monte-Care Carlo estimator in the
horizon, discounted setting is
T hB 144
+ 0² 12t + +0(1)++((B))) +O (19)
MS B,T) = C3 (AI...., An, 0
under the assumption that 7:= = o (h+).
The different terms in Corollary 4 correspond the estimation error, the approximation error and the truncation error as in the scalar case. The optimal step size choice exhibits the same dependence on and as in the scalar case, but with a different constant depending on the eigenvalues. Lastly, the general case for Langevin processes with stable matrix A is discussed in Appendix D.3.
4 FROM LINEAR TO NON-LINEAR SYSTEMS: A NUMERICAL STUDY
The trade-off identified in our analysis suggests that there exists an optimal choice of the temporal resolution in policy evaluation. Our next goal is to verify the trade-off in several simulated dy- namical systems. While analysis assumes linear transition and quadratic cost, we empirically demonstrate that such trade-off also exists in nonlinear systems. For our experimental setup, we choose simple linear quadratic systems mirroring the setup of Section as well several stan- dard benchmarks from OpenAl Gym (Brockman et al., 2016) and MuJoCo (Todorov et al., 2012). Our findings confirm the theoretical 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 demonstrate the trade- off analyzed in the previous section, the results of this experiment are shown in Fig. For all the systems, we fix the parameters o² and Q I. The lines in the plot represent the sample mean (Var(h) (h) 2 and the shading represent standard error of our sample means. Each data point was averaged over 50 independent runs in the scalar case and 40 the vector case. We observe a clear trade-off in all the Fig. plots. Fig. ((a) shows the MSE in an one-dimensional system with T = 8 and a = -1 The ground truth V calculated analytically by using Eq. 27. The figure illustrates how the error changes as we vary the data budget. B = {2 213 24, 2215 2,16) and also illustrates the improvement that can be obtained by increasing the budget. As we increase B, both the error and and the optimal step size, h², decrease. This result aligns with the analysis shown in Theorem
7

---

Under review as a conference paper at ICLR 2023
and Corollary 2. The objective is minimized when h is chosen appropriately. Fig. 1(b) and I(c) show the experimental results for both undiscounted finite horizon and discounted infinite horizon multi-dimensional systems. Calculating the ground truth V for our nulti-dimensional systems is more involved than in our scalar system. To calculate V for the undiscounted finite horizon system, numerically solve the Riccati Differential Equation using backwards induction is standard practice. To calculate V for the discounted infinite horizon system we solve the Lyapunov equation using a standard solver. Note in our experiments the dimension n 3. We fix all parameters and run our experiments on the system A = cI3 where E (-0.2, -0.5, -1, -2, -4}. producing stable systems with different eigenvalues. Results in both plots suggest that the impact of these eigenvalues of A on h' is mild and that the eigenvalue-dependen constant terms in Corollary 3 in our vector analysis do not significantly affect the optimal step-size h², The eigenvalues do influence the values of the MSE achieved in each system. MSE decreases as the magnitude of the eigenvalue increases. In the infinite horizon system, the horizon needs to be large enough to manage truncation error while simuitaneously being small such that we can run multiple rollouts. We choose y large enough such that we can learn a good estimate of V. We set T = 1/(1 - 7), which is commonly referred to as the effective horizon in the RL literature.
T-8, am-1.0
T-2, B-4096
T-20, B-16384, y-
1024
101
100
(Vvgh)- V1
(We00)-
10-1
102
B-4354
10-2
10-1
10-4
10-3
10a
10-2
20-1
10
(a) 1 1, finite horizon
(b) 72 3, finite horizon
(c) n 3. infinite horizon
Figure 1: Mean-squared error trade-off in linear quadratic systems of different dimension n. The left-most plot shows the dependence of the optimal step-size on the data budget; as expected the optimal step-size decreases with more data. Middle and right plot show the MSE for different drift. matrices A. Note that the optimal step-size h exhibits only mild dependence on the scale of A.
4.2 NONLINEAR SYSTEMS
We empirically show that the trade-off identified in linear quadratic systems carries over to nonlin- ear systems, with more complex cost functions. We demonstrate it in several simulated nonlinear systems from OpenAl Gym (Brockman et al., 2016), including Pendulum, BipedalWalker and six MuloCo (Todorov et al., 2012) environments: InvereedDoubleeendulnm
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 to the underlying continuous time systems. We train nonlinear policy parameterized by neural network for each system. by the algorithm DAU (Tallec et al., 2019). This policy is used to gather episode data from the continuous-ting system proxy at intervals of St 0.001 which then down-sampled for different h based the ratio of h and St. This allowed to handle uniformly all environments, thus yielding the behaviour of the MSE with respect the sampling time in the same interval. The policy is stable in the sense that it produces reasonable behavior (e.g., pendulum stays mostly upright; Ant walking forward etc) and not cause early termination of episodes (e.g., BipedalWalker does not fall), in the continuous -iim system proxy. The results of the MSE of Monte-Carlo value estimation are shown in Fig. 2. Similar to the linear systems case, we vary the data budget B and see how the MSE changes with the discretiza- tion h. 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 at öt = 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 (200 steps for Pendulum and 500 steps for WipedalWalker). Please refer Appendix F for more details the setup including B, T, 8t, h.
8

---

Under review as a conference paper at ICLR 2023
Funduumii,, Tw10
B pedaa We Jor-2, Tw10
InverteDoub www.n.uu-md........ Tw50
Pusharn, Tw50
13-
1977
27.
184h
23
55.5
1877
12
157
10
39
Si Sammorss, Tw40
Nosperv2, Tw0
hulCheriahvi, Tw50
Ant-13, Tw50
392
10"
180
12
187 16" 237
22"
127
Sample Budget
- Bo -
x Bo
- 5 x Bg
- 10 x Bo
- 20 x Bo
Figure 2: MSE of Monte-Carlo value estimation 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). Bg denotes the environment chosen such that it gives a full episode for the smallest h (see Appendix F). almost all environ- ments the optimal step-size depends on the data budget (with diveerteDDuubeeeenduuun the only exception). particular, the MSE as a function of h shows a clear minimum for choosing the optimal step-size, which generally decreases the data budget increases.
base sample budget,
being
These system are stochastic in the starting state, while having deterministic dynamics. Despite the different settings from our analysis, clear trade-off is evident in all systems.
Optimal Step-Size in Nonlinear Systems Fig. 3 plots the empirical h" over B for all nonlinear environments, and fitted lines based on the relation h- c -1/3 1133 for finite horizon undiscounted linear systems described in Corollary 3. The plot shows that the analytical trade-off for linear sys- tems is observed approximately even the non-linear experiments. The constant e depends on the system parameters (and the policy) and, as expected, varies with the environment. In our experiments, c ranges from 0.02 to 0.2, which serve as a starting point for optimizing the step- size in other experiments.
Pentukumed
5 Spelahrukes
Freetted chendu umoz
Pusher22
Switmmr-d
10a
crgetn
Figure Empirical h" nonlinear experiments (solid lines) aligns well with the analysis in Corollary (dashed lines): h" = cTB- 1/3, is environment de- pendent and estimated from the data by least squares.
CONCLUSION
We provide precise characterization of the approximation, estimation and truncation errors in- curred by Monte-Carlo value estimation in Langevin dynamical system with quadratic cost. Our analysis reveals fundamental bias-variance trade-off, modulated by the level of temporal discretiza- tion h. In a second step, we confirm in numerical simulations that the analysis accurately captures the trade-off precise, quantitative manner. particular, we show that the trade-off carries over to non-linear environments such as the popular MuloCo physics simulation. Our findings show that managing the temporal discretization level can greatly improve the quality under fixed data budget B. This has implication for practitioners, as in most environments that we encountered the step-size is typically pre-set and rarely changed. There are several interesting directions for future work, including considering policy optimization and other value estimation techniques such as temporal differencing and system identification. Another direction is to extend the analysis non-linear systems via local linearization.
value estimation

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yasin Abhasi-Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Sham M. Kakade and Ulrike von Luxburg (eds.), Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Re- search, pp. 1-26, Budapest, Hungary, 09-11 Jun 2011. PMLR.
Srikhar Bahl, Mustafa Mukadam, Abhinav Gupta, and Deepak Pathak. Neural dynamic policies for end-to-end sensory motor learning. Advances in Neural Information Processing Systems, 34, 2020.
Leemon C Baird. Reinforcement learning in continuous time: Advantage updating. In Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN" 94), volume 4, pp. 2448- 2453. IEFE, 1994.
André Bardow. Optimal experimental design of iol-p problems: The meter approach. Computers 124, 2008.
& Chemical Engineering,
Hildo Bijl, JaanJann-llllee Willem van Wingerden, Thomas B Schön, and Michel Verhaegen. Mean and variance of the lag cost function. Automatica, 67:216-223, 223, 2016.
Steven Bradtke. Reinforcement learning applied linear quadratic regulation. In S. Hanson, J. Cowan, and C. Giles (eds.), Advances in Neural Information Processing Systems, volume 5. Morgan-Kaufmann, 1992. URL
http://prrooeddnn.............p. neurips. ctciiss.ccppaaae pttpppp//199/////////
Steven J. Bradtke and Michael O. Duff. Reinforcement learning methods for continuous-time Markov decision problems. Advances in Neural Information Processing Systems, 1994.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, arXiv preprint arXiv: 015400 2016.
Tongyi Cao and Akshay Krishnamurthy. Provably adaptive reinforcement learning in metric spaces. Advances in Neural Information Processing Systems, 34, 2020.
Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: review. Statistical Science, pp. 273-304, 1995.
Will Dabney, Georg Ostrovski, and Andre Barreto. Temporally extended e-greedy exploration. In Proceedings of the International Conference on Learning Representations, 2021.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, 31, 2018
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu, On the sample complex- ity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-679, 2020.
Kenji Doya. Reinforcement learning in continuous time and space. Neural computation, 12(1): 219-245, 2000.
Greg Droge and Magnus Egerstedt. Adaptive time horizon optimization in model predictive control. In Proceedings of the American Control Conference, pp. 1843-1848, 2011.
Maryam Fazel, Rong Ge, Sham Kakade, and Mchran Mesbahi. Global convergence of policy gradi- ent methods for the linear quadratic regulator. In International Conference Machine Learning, pp. 1467-1476. PMLR, 2018
Ian Ford, DM Titterington, and Christos P Kitsos. Recent advances in nonlinear experimental design. Technometrics, (1(1)::9-600 1989.
Tryphon T. Georgiou and Anders Lindquist. The separation principle in stochastic control. redux. IEEE Transactions on Automatic Control, 58( 11):0021211-49999 2013. doi: 1091/09/A...011. 2259207.
10

---

Under review as a conference paper at ICLR 2023
Shixiang Gu, Timothy Lillicrap, Ilya Sutskever, and Sergey Levine. Continuous deep q-learning with model-based acceleration. In International conference on machine learning, pp. 2829-2836 PMLR, 2016.
Yunhan Huang and Quanyan Zhu. Infinite-horizon linear-quuadrati-ggaasiiaa control with costly measurements. arXiv preprini arXiv:2012. 14925, 2020.
Yunhan Huang, Veeraruna Kavitha, and Quanyan Zhu. Continuous-time markov decision processes with controlled observations. In 2019 57th Annual Allerton Conference on Communication, Con- trol, and Computing (Allerton), pp. 32-39, IEEE, 2019.
Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis. The dependence of effective planning horizon on model accuracy. In Proceedings of the International Joint Conference on Artificial Intelligence, 2016.
Jeongho Kim, Jaeuk Shin, and Insoon Yang. Hamilton-Jacobi deep Q-laarning for deterministic continuous-tiin time systems with Lipschitz continuous controls. Journal of Machine Learning Re- search, 22, 2021.
Karl Krauth, Stephen Tu, and Benjamin Recht. Finite-tima analysis of approximate policy iteration for the linear quadratic regulator. In Advances in Neural Information Processing Systems 32, pp- 8514-8524. 2019.
Aravind S. Lakshminarayanan, Sahil Sharma, and Balaraman Ravindran. Dynamic action repetition for deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2017.
Jaeyoung Lee and Richard S. Sutton. Policy iterations for reinforcement learning problems in tinuous time and space - fundamental theory and methods. Automatica, 126, 2021.
Frank L. Lewis, Draguna Vrabie, and Kyriakos G. Vamvoudakis. Reinforcement learning and feed- back control: Using natural decision methods to design optimal adaptive controllers. IEEE Con- trol Systems Magazine, 32(6):76-105, 2012. doi: 10. 10.1109/MCSAA SAT..I....1...2211...
10.110//CC52012222144
Anders Lindquist. Linear stochastic systems (peter e. caines). SIAM Review, 32(2):325 328, 1990.
doi: 10. 10.1137/1032067. URL https: /ww.oooooooooooooooooo org/10
Michael Lutter, Shie Mannor, Jan Peters, Dieter Fox, and Animesh Garg. Value iteration in tinuous actions, states and time. In Proceedings of the International Conference on Machine Learning, 2021.
Alberto Maria Metelli, Flavio Mazzolini, Lorenzo Bisi, Luca Sabbioni, and Marcello Restelli. Con- trol frequency adaptation via action persistence in batch reinforcement learning. In Proceedings of the International Conference on Machine Learning, 2020.
Francesco Mezzadri. How to generate random matrices from the classical compact groups 2006. doi: D0.8550/AKXX.MMATHHPPP00000 0609050.
URL //tpiii////iiv./// org/ abs hattthhpphh//
Rémi Munos. Policy gradient in continuous time. Journal of Machine Learning Research, 2006.
Rémi Munos and Paul Bourgine. Reinforcement learning for continuous stochastic control prob- lems. Advances in neural information processing systems, 10, 1997.
Mojmír Mutný and Andreas Krause. Experimental design for linear functionals in reproducing kernel hilbert spaces. arXiv preprint arXiv:2205. 13627, 2022.
Mojmir Mutny, Johannes Kirschner, and Andreas Krause. Experimental design for optimization of orthogonal projection pursuit models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10235-10242, 2020.
Seohong Park, Jackyeom Kim, and Gunhee Kim. Time for policy gradient methods. Advances in Neural Information Processing Systems, 34, 2021.
invariant safe action repetition

---

Under review as a conference paper at ICLR 2023
Sahil Sharma, Aravind S. Lakshminarayanan, and Balaraman Ravindran. Learning repeat: Fine grained action repetition for deep reinforcement learning. In Proceedings of the International Conference on Learning Representations, 2017.
Sean R. Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Adaptive discretization for episodic reinforcement learning in metric spaces. Proceedings of the ACM Conference on Measurement and Analysis of Computing Systems, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Corentin Tallec, Léonard Blier, and Yann Ollivier. Making deep q-learning methods robust to time discretization. In International Conference Machine Learning (ICML), number 97, pp. 6096- 6104, 2019.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference intelligent robots and systems, pp. 5026-5033. IEEE, 2012.
Stephen Tu and Benjamin Recht. Least-squares temporal difference learning for the linear quadratic regulator. In International Conference Machine Learning, pp. 5005-5014. PMLR, 2018.
Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. In Conference on Learning Theory, pp. 3036-3083 PMLR, 2019.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nel- son, Eric Jones, Robert Kern, Eric Larson, Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, lan Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mul- bregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 10.
Haoran Wang, Thaleia Zariphopoulou. and Xun Yu Zhou. Reinforcement learning in continuous time and space: A stochastic control approach. Journal of Machine Learning Research, 21(198): 1-34, 2020. URL http:////// jmlr.
/ wwwlv1-1liie 144 html.
Cagatay Yildiz, Markus Heinonen, and Harri Lähdesmäki. Continuous-time model-based reinforce- ment learning. In International Conference on Machine Learning, pp. 12009-12018, PMLR, 2021.
A WARM-UP: THE RIEMANN SUM APPROXIMATION
The Riemann sum approximation is standard argument that we reproduce here for completeness. Let [0,7] + R be continuously differentiable function. Assume that we wish to approximate the integral I." g(t) dt using the Riemann difference is readily computed up to first order as follows:
over N T/h elements, Σ hg(h)). The
D
g(t) dt h
N-1
(i+1)/
g(() g(ih) dt.
N
<
g'ihh) 1+ O(1)) di
+
2
12

---

Under review as a conference paper at ICLR 2023
A naive bound is obtained as D < N h² |l O(Nh²). Translated to squared error, this explains the dependency ( (²)
In the case of discounting, let g(t) = 7f f(t) and g'(t) = -((((t) + f())). Hence, the previous display leads to the bound
N-1 D Σ
th (ft + f( + 0(hh))
2 1=0
1 - Nh [s(()) + M()I + 0(19)
2(1 7R)
Overall, the squared error is now (1h 2 O log(1/7). Note that this alone does not explain the improvement of the order from 1t2 to 2 which requires that also [(() is decaying fast enough.
B
MOMENT CALCULATIONS
Recall that the solution of the SDE in Eq. (9), with (0) 0, takes the following form:
(1) [ (a(t=)) dw (s).
(20)
An integral part of finding the mean-squared error of the Monte-Carlo estimator the computation of the moments E [z)() 1E [=(t)] and E (x(()²x(t)²) when s S t.
Lemma 1. Let xxt) be the solution of Eq. (9). The second moment of the state variable is
σ² (e2at - 1)
[[) =
(21)
2a
For the forth moment, we get:
30 4
E (1))*
(c - -1)²
(22)
4a
Assuming that S t, we further get:
E (s)x
- (e2as 1)e {(e 2as c -2at) +(1 - -2ax)]
0²
(23)
4a²
Proof.
(1) We start with the second moment E [z(t)?].
2o2 [ dwo(s)
2 ( e-2a ds
0² (c 1)
E [cttt]]
2a
The calculation makes use of the Itô isometry, which can be stated as:
E [ (s)) dw (s) ]
E 2(3) ds
(24)
for any stochastic process 2(.) adapted to the filtration induced by the Wiener process w (-).
(2) Next we compute E [=<(t)]] through Itô's integral. Define y (t) = Ji e eaa dw (u), so that
dy (1) -at dw (l). Thus,
a =0 (v dy (1) 1mm (v) dy (1))²
= (v((w()) ed at dw (1) + 1" 5" (v)) 2at dl,
13

---

Under review as a conference paper at ICLR 2023
for any f ()) By choosing f (1) y
(2) 4y and (" (v) 12y².
Therefore, by integration and taking the expectation:
L f' (y (u)) e dw (u)
E Jo f (y/ (u)) e- 2au du
[f (y [t)]= =E
(1% e- dw (t) an dw (u)
I e-v dw (0) )
E
+ B
12
2au du
0
6F
aaa a dw (v)
du
f
27 du
6
E
e- dw (1)
(Itō isometry)
6
220 e 2av du du
1
2an
e1-e-2au) du
0
2a
3
(1 e 22t)2
4a
From Eq. (20) holds x (t) = oe y (t) so that the second part of the lemma follows.
33) Lastly, we compute xx))) for St.
(s) x² (t)] = o 20(++00 (Nr e dw (u) )² (1¹ e au dw (u)
27 )
e-au
(Jo aa dw (u)
(Je e -au dw (u) + fr c--a dw (u)
27
o" 2 20(
E [[ e an dw (u)
+E [So -an dw (wi)
27
o 20(s+e)
e an dw (u)
(i)
Note that computed (i) before. For (ii) it holds:
/ 2au dw (u)
E
dw (u)
(1 e 20s
2a
and
( -au dw (u)
27
{" e -2au dw (u)
E
1
-2-aa 20s -2at)
2a
Therefore, assuming it holds that (it is necessary Itô integration in this case):
E 2 xs) (t)] R A 2a(++))
1
(e (c-205 c + 4a
(1
20s
4a
daz "
(e 2ae {Ce-2at - -200) +(1 E 20t e-20t)
14

---

Under review as a conference paper at ICLR 2023
C CALCULATIONS OF THE MEAN-SQUARED ERROR
C.I UNDISCOUNTED, UINTE-HORIZON PROOF OF THEOREM 1
Proof. We first note that
h N-1 M
N-1
Σ
(khh) = h Σ (kh))
1=1 k=0
where we denote x(t) = (t) for simplicity. Next we expand the mean-squared error
B[(V (h) VT B (h)]
(b)]++++ +1
1
N-1
1 2VT +
-
Σ (k(h))
E
M
h²
N-1
(ki(( - 2V7B/Va + V22
B|a
M
15j k,,=0
h
N-1
M - M
M (kh)r
Σ
EE
V?
M
For the last equality, note that - the expressions. By Lemma I we have for the second moment of the state variable:
B( (1h)). It remains to compute
E [t)
(e2at
(25)
2a
Assuming that s S t, from the same lemma we get the following for the forth moments:
0¹ 2c 1)e {(c ((e-2as 2as - e 22t) + 3(1 e -20s)}
E[ (8) (1)
(26)
4a
Note that by symmetry, a similar expression follows for Using these expressions, for the expected cost we get
Vr / (l)
o² / (620t - 1) 2a
(27)
2a
2a
We remark that a similar expression was previously obtained in (Bijl et al., 2016, Theorem 3). Next, the expected estimated cost is
N-1
N-1 0²1
0²h
1
2aT
E[Vas (h)) = h Σ k=
[kh)(
Σ
(
2akh -
N
2a
2a
2ahh
0=
Lastly, it remains to compute the sum
h N-1
24t N-1
h²2 N-1
E E (kh)a
Σ
E[h2(2))2
Σ
Exx (kh))
E
M
M
M
k,1=0
kel
A=
TT 1i2 (c2aT - 1) 28h + 20 + 1) + 2 2ah 1) 2
2hT (E2ah 1) (e2ah 55
4a2 Bh (c2ah 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 calcula- tions in the supplementary material. It remains to collect all terms to get the final result.
15

---

Under review as a conference paper at ICLR 2023
C.2 UNDISCOUNTED, HORII-HO STEP SIZE
Although the exact optimal step size h" can be obtained from Theorem 1 in practice, such exact A* doesn't have an explicit solution through Theorem 1. A trivial way to the order of h" in terms of B, a, T is finding the dominated term by using Taylor's 's expansion for exponential parts (which is true for any h) in Theorem 1. A proof of Corollary is given as follows.
Proof. From Theorem 1, we compute the leading terms in h of the least- error:
E (T,,,T,)) o (c2aT 1)² h + +11"),
(28)
16a
E2 T,a) o'T (4aT - ee + ea
(8a'f - 4) +5)
1
o 'TT(1 gdo'l + 4all 4al'
Sat
hB
4
T'Th (1 4aT + 20 (8aT +4) -5taT) o o'Th² (CnTT - + 0 (h
24a²
12aB
(29)
is trivial to see, when h 2 1, both Eq. (28) and Eq. (29) will blow up, and increase exponentially in h. Thus, a small h < 1 is considered to minimize Ej (h. T,a) + Ez(h.T,a) Keeping the first term in both Eq. (28) and Eq. (29) and solving for the optimal h" yields the result.
A more precise approximation of ht than Corollary 2 is a minimizer of (i, + T.(h.T.a) truncated at (h²)):
B
D1
D
3D2
9D3
DJ D2 9a D
h² (a, T, B)
3Dg
33 3
2a²
V
4a D3
D
3D2
9Dg
D2
+
(30)
3
Da
4a D3
9a² DJ
where
D1 = T (1 + TaT + 20T (8aT + 4) - 5c 407)
D2 = T (AaT ACT + 6 2nT (8aT 4) + 5)
D3 3B (e 1)3 - 4aT 1).
We can further express Eq. (30) in terms of B, as
1/3
T (4rT - e ATT + e 2aT (8aT 4) + 45)
h²BB)=
B-1/3
a² (c20l - -1)2
T' (1 + 4a7 4eT + 2nT (8a'l 4) 55A07)
4aT + 1)D 1/3
B B-4/3
9(c2aT - 1)2B
9a2/3 - 1//3/3
(aTT 1) +-2+ O-B-03
27(c2aT - 1)3
where the first term is exactly the result in Corollary 2.
C.3 FINITE-HORIZON, DISCOUNTED
As stated in Section 3.1, adding discounting in the saite-horizon setting makes the mean nean-squared envor more involved. In the regime where h is small and B is large, Taylor expansion characterizes the error surface as follows:
TT
1 o J42221 2T 222 - -1)2 122
MSET (4, B,7) R3
log())(( + log(r)) log(>))² hB +
16a2
n" (120T - 1) (T" (620T (2a + log (7)) log (7)) - 22a)
h33 0
48a
144
(31)
16

---

Under review as a conference paper at ICLR 2023
The approximation shows only the lowest order terms for (/BB,, 7f and h. The derivation is given Lemma below. The results shows that main trade-off between h and B persists also for the discounted objective, long 7 is treated limit where 7" becomes small (e.g- 7f = o(h²)) the nature of the trade-off changes in that the approximation error improves to O(h*), ). 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 factor N, thereby removing factor of 1/h from the (non-squared) approximation error (see Appendix A for more detailed explanation).
constant relative to h² and 1/hB. In the
Lemma 2 (Finite-horizon, discounted). In the finite firize- with discount factor (0, 1] set- ting, the mean-squaree error of the Monte-Carle estimator is
MSE B,7) Eh,,, Eg T, T,,,))
where
= - C2( + ( Ca(T, o'h't +0(h)
144
*T + C,
E2(h,T,a,n) log(t))( (2g log(7)) 07
G(T,7,a) 7-8 (c20T= - 1)
16a²
C2(T,,a)) 77 (620T -1) (1 (c2aT (2a + log(?)) log(n)) -2a)
48a²
اtوot [it (e2a'l (2a + log(n)) - 1og(>))) 4a (62aT + log(>)) log(7))
CT(T,
576a²
Ca(T, 7.a) 3) is some finite constant of (T, Yi a) that includes T as a factor.
Proof. The proof follows the similar computations those in the previous proof with new ex- pected cost as follows. In particular, using Lemma 1, we get
VT = 1' "'E
0² (TT'2al' -1 x² -
(32)
2a log(7) 2a log(7)
Furthermore, the expected estimated cost is
o2h N-1 Σ Ah (2aakh -1)
02h (1 7 T2aaT
1 g-
(b))
2a
2a 1
nhh 22ah
1 1- g/)
Finally, the containing the forth order cross-moments is
24
N-1
422
N-1
kht kh+ (("h))
Σ ke
kh (l23
+
Σ k=0
x 2kl Bla
(kh)]]
M
M
M
k,
While not impossible calculate paper, written derivation is beyond the scope of this work. Instead, we rely on symbolic computation to obtain the expression and corresponding Taylor approx- imations. The notebooks containing all derivations provided in the supplementary material. I
17

---

Under review as a conference paper at ICLR 2023
C.4
INFINITE HORIZON: PROOF OF THEOREM 3
Proof. The proof relies on the decomposition provided in Eq. (17). It only remains to compute the following cross term.
Vi (h)
V/
o²
7-
7 2a2
h
7 eal
1 - 72
1
7 E22alll -1 )² -
2a
log(7) log(>) + 2a
2a
Ahe
1- 7h
2a log(?) 20 log(7)
o o (c2aT - 1) (log(?) (e2aT
-1) 2a)
ht
8a log(7) (2a + log(>))
o (2a + log(n) 2a log(7)) (2a (? Ea 1) + (og(o))))))))) (e2aT - 1)) h²² + 0hh))
48a² log (2a log(7))
Thus, the mean-squared error MSE (h. B, T.T) = (V) - Voo)²) is obtained by combining the above computation with Eq. (16) and Lemma
D VECTOR CASE ANALYSIS
D.1 FINITE-HORIZON, UNDISCOUNTED. PROOF OF THEOREM 2
Proof. Consider the n-dimensional system that the solution of the trajectory of X(t) is
X(t) = a S( ((l-->) dw (t).
Since A is a diagonalizable matrix, we can decompose A as A = P-DDP where P is a invert- ible matrix (not necessarily be orthogonal) and is diagonal matrix whose diagonal entries (AI...., ;,. are corresponding to the eigenvalues of the matrix A. Followed by which, we can decompose the matrix exponential of A as:
ct p-1 p
Define the "diagonalized" process X (-) as:
PX (t) = Po A(C-s) dW (s)
= app-1 S' Dit-o) p dW (s)
=o 1/ D((--)) aw (s) = X (t)
where W. (s) is Wiener process (with dependent components when P is not orthogonal). This implies that X (.) x-1X(()
To see (t) clearly, we denote P = [poli and X((t) = (t).
(t)) then (t) = Ej= Pijor cA((tss) du (ss for each E {1,...,,)) n). Particularly, in such an ex- pression, " are independent Wiener processes for different i or j. Correspondingly, X(t) = (I), ... on (1)) and (I) = E Pl fo ci(t-s) dwy(s) for each I E {1,-.. ,n], where (s) are independent Wiener processes for different j.
By trace operation, we can rewrite (hr(h) as follows:
M
N-1
(hr(h) = M
Σ
hx (tx) QX (1x)
k=0
M N-1
tr 1
hx T 1
M
i=1 k=
1 (h) tr (P-TQP
18

---

Under review as a conference paper at ICLR 2023
where Vas (h) 114 Ei= En=o hX (tx) (tx) E R Similarly, Vrr - ir (PPTTP-- QP-QQP---- vr} J. where VT - So ([ dl.
Therefore, the MSEr(h, B) can be written as
MSET (h, B) = IE (1) V/r) -v
=B =B ir
p- (r(p-TQQ--) QP-1 (bxr (1)) - 11) }²)
(33)
For notional simplicity, we denote matrix P- p--TQP-1= =: B = =Myl];-= and Vas (h) Vy= =: [ay]ī)=1-
Noting the fact that
27
(,, = EE
Σ 2
byrcyy
Σ
(34)
Indiaade
is sufficient to find MSET by only computing [ct, (t We first introduce the following expectations that are used in the computations. For any s S
xi(--u) duc(u) !-" dd(l--u) dw((w)
ex
(1- -((-talld2))))
E
(35)
A1 t1
cdl duolu)
/ (a dw(u)
l/² dd((t-u) dw(u) J cdllt-w) dwv(w)
E
1 (11 + 1-)22 21)
(1- (1 (1- -- 1 1 (1-e-(httda)) (1 - ( (1-e-(atd2)
1
+ (A1 + As + da)
(1-e-(itdii)) (1-e-(hetb)))
(A1 + Aa) + As)
1- (e-(ssthi)s e c- -Aott)01t)
+ +(11 + (2s + 21)
(36)
T
[ 2x (x:((-w)
dw(()) dwl(u) / exa(-w) dw(u)) dt
eliitda) - 1 -(x1 + +22)T
E
(37)
(A1 + \2)²
By using the definitions of DM (h) and Vr. it is trivial to see for any 1.j E ,1.
M
N-1
L-² (1))())))()) di
Ctj =
ho
(khi)
M
km
h
M
N-1
tb
[ Pja e (di(k dul (s)
crlkk ds)
Pla
M
K=0
a=1
Pio (' (il-s)) dowals) (8)
Σ Pja L' eds((t=s) dwals)
E
dt
a=2l
12
ho²
Ahh
(So
Ah
Σ
(d((hh-a) durll
edu((in cleufi (s)
PloPjo
M
K=
T
cilt-a) dwals)) (fo cis(t-o) dwra(s)) dt
E
Σ PiaPi8
ho2
M
N-1
% phh
(i duol((s)
(1.m) (du(thho)) du))(s) }
M
K=D
19

---

Under review as a conference paper at ICLR 2023
where the last equation is due to the fact that for B
E [[. chlt-s awals)) (So cls(e=0) dwg(s)) )] 0.
Thus, for any 4 J1.32 E {l, nn).
E B(etis A252)
Σ Phaa PhaPiaaPPaPPaa I (M,h,7 T, T,, 2o3 0))
Σ
Pla PhaaPhaPlaSPis00 Iz (M, h, T, A12 Aiv A129 A32 02, 3)
agt a +
Ph PhoPhhsPtooPhoo (M, h, T, Ar, Agu X A32 a, 3).
(38)
a
where
I (M, h T, An Anr
Ata dja
M
N-1
(So kh
E
h
ed (k) dw! (s) (w))(s) A (t-s) dwals) (% coiiltts) drealss)
enss (Kh- duo (s)
M
k=0
E
dt x (k dood (%oa) (dislionm)) ds)
h
M
N-1
(Ssa kb
M
K=O
!'"
()1g(t=)) dwa(()) (1o (dra(tme) dwal()) ) dt
E
and
Iz (M, h T, A A3s Alas Ajs: at, 3)
M N-1
kh eddes (k)--0) dwo (lod)(()) (s) ) Ars (e-s) (t-o) (o) (To eni (eateess) (twco(o)) ]] de x
(1,0) kh
en (A0--)) duo (s)
=
M
[.
h
M
N-1
khh (khh drolf((s)) (s)
(%.a)) edvelkh-ss s) doo (2) (s)
M
i=1
K=D
(1- dup(s)) (1o ediall-e)) dwoo(s) ]] dt
E
and
Is (M, h, T. Ar,
Aji Alz. A5zi at, 13)
M
N-1
ed (Kh (kh do) (s))
(f,a))
th
cin Cin(Ahh (kh- 5) dwy
(0 (s)
= E
x
M
k=0
N-1
(%oae) (tts( duy (8) (3)
hh
}
(thh (s)
M
K=U
20

---

Under review as a conference paper at ICLR 2023
Note that ( and wa are independent for a + B. By using the expectations Eqs. (35) and (37),
(
we can further obtain I2 (M, T, Ar. A 122 a 8) as
I2 (M, h, T, A A/2 Al2 A/2 ()
+h,, yr
T
(elAn (c(An+An)TT - (A1, + X31 )T)
(Ar, )11))
1 el (AA +As1)> )a
(A,, + tg1 h)
h
(d Aigtt)s
T)
1
(elMgthaa) -1 1- (A12 + >33))
(A1z + )52)
(A t222 h
(Ar, + Aja))
In the following computations, we will use C' and C(2 Xo1 Nla A12) to represent some constants that are not depending on h, T, B.
The expectation Z (M, h, T, >1, Aii Atg, Aia a) is computed exactly the same way as in the proof of Theorem by using the expectation results Eq. (35) and Eq. (36). Notice that the ex- pectation result Eq. (35) (when s = t) has the same order in as the expectation Eq. (25). Moreover, the two expectations Eq. (36) and Eq. (26) have the same orders s and t. Thus, I, (M, h, T, X Ais Au Ai a) has the same orders in h, T, B as the scalar MSE, i.e.
I1 (M, h, T, At, Ai Alao a)
(C1 + C1 (A,,, Aa. N )12) ((T)) hh + O(h))
T
1
+ (C2 + C2 (A1, An Ae )12) O(T))
+ 0
hB
B
The expectation Ig (M, h, T, A,, 2ú, Nb. Ajz, 0, B) can be computed directly and has the result:
( ->,,) -1 (e(Aes +Apa)T (e(deytra)t - 1) 122
La (M,,,T, N1, As. des A32, a, 3)
+ +hh9)
4 (A, + A11) (A12 + )12))
-(170 + Ca(Ai, A5. Ao. Ais )((T))) 122 122
- 0(h))
The expectation I3 (M, h T, Ar, Agr Als Asai 0, B) can be computed as follows:
Ig (M, h T, Ae Air dea Ais= ())
(A - N1, )nh -1) 1)
(A (AAs - -1) h2
2 n
M
(11, + Nea) (1i + 2122)
k=0
h?
Ax Aight kh+ Aig
(1- (2 (1 e- e(As +22
-Anntdss)aa)) )bh)
M
(A1 Noa) (Ai + diz)
R<C
h
a h gh+ kh
(1- - (212 (N-e-(A )kn (1 e- (22
M
(Nu, + No.)) (A,, + +1aa)
kCn
T hB 2 B
(C₁ + C1 (Ar, Ap. Mr, An))
Thus, the final result is obtained by the expression of MSE in Eq. (34), Eq. (38) and the above computations. Again, we rely on symbolic computation to obtain the expression and corresponding Taylor approximations and include the notebooks of all derivations in the supplementary material.
The extension from Theorem 2 to the discounted finite-horizon results can be done in the same way as in the above proof (add the discount factor y in VMr) by using the expectation cost for any \ and Ag:
S""
1 A S (i((t-u) dw(u) y (c( -
' cda(-a) dw(w)) dt
TT TT-17
()) x²)
log (1) + (hi X2)
log (7)
21

---

Under review as a conference paper at ICLR 2023
D.2 PROOF OF COROLLARY 4
Proof. We shall follow the similar proof as in the proof of Theorem and the proof of Theorem 3.
Continuing from Eq. (38), in infinite-horizon discounted setting, we have
I (M, h, T, At,
Ajr
Alg A52:7.a)
h
M
N-1
kh (%.ma Ahh
enr (h (kh-a) dw) ) (1. kh edni (kh-s) dood" (s)
E
M
k=0
Ani(t dwoals) (Jo edsi edtilito) ducass)) dt x
Y
'E
h
M
N-1
Σ khh (foee (Kh)( duw)(())
(%,m) edsa(thh-o) drol (o)
M
K=D
! 7'I
I(. / ( dwalls) ) (% edss(ltt)) duca(() (o)c(t)]] de a0..
and
I2 (M, h T, Ar, Ajr A121 Ajs, Y, Cr, 3)
( thss) )
- 7.
1
1
(1, + )5.)
1 - ( +>ss))))))s))0 thss)
- 7h
()e, 2z.)
log (r)
log (7) + d + AÚs
h
- n cA -2/2)
1 1-
1
1
1
x
(Dr + )jo)
- (ele -2 +
1 1h
(A1z + )dz))
log (7)
log (7) + A1z + Ajz
and
Ia (M, h. T, Aty A3i
Alar djsr T. ar
M N-1
(1,
E
h
Σ
7
Mh
dee (kh dool (s)
ed (Ah (hh- duc (s) (s) x
M
k=
h
M N-1
Σ
kh
khh
(k
duoll (s)
kh
( duo (3) (8)
]}
M
1=1
k=
Similar arguments as in proof of Theorem 2, we can conclude I, hM, T, At, din Aegs Ajoo (.) has the same orders in h, B, T the MSE result in Theorem 3.
Moreover, let C, Ais Ala Ajzs 7, TY'''s 's are some constants that depend on dir Aego Aj2 7, T, then
Is (M, h T, dr, Agi Al 23,
σ pT (CI(A,, des Ais T) + C2(Ai. Ae. Na. 7, T)h)
+ (Ca()i Ae, Ap Th? + Cilde, : de 2er v, T)h²)
to! (1 1
+ + Ain No. N3) 77) na 0(1)),
144
22

---

Under review as a conference paper at ICLR 2023
and
Is (M, h, Na, Agrr Alzs A3z 7, a.
(o (elon +D2 )ah -1 (clAsttAs)) +A2)s - -1) 12 n22
h2
N-1
Σ
M
Oun + )12) (Asi + )1a))
k=0
42
Σ
e Ahi gh Ah
(1- (Ar (An+)12)) (1 (1- -Aoss (Ass+)ss)RR) yi
M
(h1, + A1a) (Ag, A322)
k<n
122
E Aez tn gho kh
(1 - -- (di (1- -Ass e (Asstd11))0 (Ass+ y(ett))
M
(Ar, + )1,) (Aj, Ajja)
k<q
7
11
Cc (At, >o, Abs A3z 7,
B
hB
The result in this Corollary is obtained by combining the above results. And we include the note- books of all derivations in the supplementary material.
D.3 THE CASE WHEN A IS A GENERAL STABLE MATRIX
Lemma (MSE when A is a general stable matrix ). Let be a stable n. X n matrix with distinct eigenvalues '1, Am and corresponding multiplicities 91,'" -9m- There exist some constants {C,) Co and C,('..'.. Am, ?1 T) s, such that the mean-squared error of the Monte-Carlo estimator in different selting satisfies
(1) Finite-Horizon undiscounted setting:
m
MSET I2 (.C.MSET(h, B,),,, CI Am, A
+ (C2+ ... Am. T))(T) o 4T243
1
0(h)))))))))) + 0 })
(39)
Bh
where MSE (h, B, 24) the mean-squared error of the Monte-Carke estimator in Theorem by replacing the drift by Xi.
(2) Horite- discounted setting:
MSET E
C.MSEEr B,,, Ca(A1,"". T
Cs(A,, ... Am, 7, T) 1 + Co(Ai, ... Am, T)a 212
(C+(A),... AnL 7, T)) 2
+ O(h)) + 0 1 (
(40)
Bh
where MSE B, n, Xi) is the mean- mean-squared error of the Monte-Carlo estimator in Lemma by replacing the drift by Xo.
(3) Infinite- Horizon discounted setting:
MSE
(C,
(Ca(Ai, Am, T, + Co(di, Ams 7, o
(Cio(A1, Am, 7, rTt + Cni(A, Am 7, T)h3) ota
+ Cia(An Am, Mo (Cis(AI, An 7, T)) σ 2n-11
Bh
0(h)) 0 1
(41)
where MSE (h, B, 7, Xd) is the square error of the Monte-Carke estimator in Theorem by replacing the drift by Ai.
23

---

Under review as a conference paper at ICLR 2023
Proof. As can the proof of Lemma 2 is based on the proof of Theorem 1 with adding discount factor y, and the proof of Theorem is based on the proof of Lemma with the decompo- sition Eq. (17). By using the same flow direction, it is sufficient to show the result in case (1) and the results case (2) and (3) follows.
Consider the decomposition of MSE in finite-horizon undiscounted setting:
MSE, = E (VM V²
= E (Vxr E
VAd
+ E
2 VM
- Vrr
2
=
E
V
VM
+
E
Va
Vi
Part1
Part2
Before the analysis of part and part 2, we will introduce the following mean-squaredd error notations for the finite-horizon undiscounted scalar case with drift A;
MSEr(h, B, A.) Var(h, A.) + Approximation(h, B,))))
(42)
where Var(h, Ax) E
v2
E
VMs and Approximation(h, B,
B,
E
VM
Vz Vz)²
For part 1:
h²
Σ
E (()
M
i...k.
1
E [K,(k)) ( (x,( E (X,(th) QX, + 2tr (QE (K) (13)
M
h2
(Khh) (xX E ((hN)
2h2
Σ ir (((M))(()) + 4h2 tr {QE (X(N))x(())]])
(43)
M
M
k<1
where the second equality is based Isserlis' theorem and the trace operation.
Notice that E
122
B
(x(()))T(XX(M)) E (X(I))QXX(I)) Xx()) thus
E
2-
E
Var
M
2h2
4h2
Σ tr ((HA)
cr [
M
M kel
To analyze the above form, we decompose the matrix A by Jordan form, i.e. A P-1JP for some inevitable matrix P and J = diag(J,, ... Jm), where Jj is the Jordan block corresponding to the eigenvalue Xi.
Notice that (kh--s) diag(e (KK- e mmh(k k)), where
kh - (kh-s)²
(kh (kh-s))t
(9--1)1
(kh (k
di(kk-o)) (ii
kh
(g. (9-2))
Combining with the fact that for any ks, L,
bhalh
E (XI)))
A(th-s) A (1h-s) ds
khhlh
p- (khh-s) Tepee e (1h-s) ds.
24

---

Under review as a conference paper at ICLR 2023
can conclude that for any & S tr QQE [X(k))((Ih)]] is linear combination of Li.s, and 22, for all j, where
L = C1,tdd
ds
eAckt + (1 e e
= -Cib
As tog
L2s = C2 (am (ldc(kto-)) (th- (l) s)8 8)00 ds.
where Cg,.g Oi are some constants and qi {0. . 1). ū3 E {0,
.9 - 1}.
For the integral in C2 as T + qj S n 1, we can have the inequality:
kh (r (kh ()) (k) (kh 8)8² (1h - 8) ds
S 1mm11 ( kb
()) ds.
(44)
Since
QQE (X(h)) "1²)
Σ II
Lighi Ligitaia
i1.J1 RJd (1,2)(1.2)
and all the terms are nonnegative. We drop all terms that include C2 factor and only include the L7 with & terms in the lower bound of part 1. That is say, the lower bound of part is E C,C, Var(h, A²).
The upper bound of part I can be obtained by replacing all CT.s factors by C2,ú,j and use the bound
given in Eq. (44). This leads to the upper bound for part 1 is (C.+Cu(A An Am (T)))) 2p2 (
Bh
For Part 2, let g(t) = E mation of g(t). by the property Riemann approximation,
on [0. Then E [Vr]]
the left Riemann sum approxi-
E
VM
Vrl =e (hTg(T)) + +
where
(e-a)) (T) - ir QQB (X(XX(( - ( lf cdle-s) (T ds do}.
which is a constant depends on λ1, ... Am, T. Thus
E
VM - 12 Ci(1, ( TT 0(h3)
which has the same order in h as the scalar case in finite-horizon undiscounted setting. Thus the result Eq. (39) is obtained by combining part bounds and part 2 approximation.
As we explained in the beginning of this proof, in the finite-horizon discounted setting, we will follow the similar arguments in the proof of Eq. (39) obtain result Eq. (40).
For the infinite-horizon discounted setting, the corresponding part in the MSE is the same as the part in MSEr Eq. (40). The part approximated by using the decomposition Eq. (17) and the fact that
V1,00 = -f [EE(x() di - ,Am)
25

---

Under review as a conference paper at ICLR 2023
To verify oo is 0(7T), find the bounds of oi by using the similar arguments in the above proof of Eq. (39) and the following inequality:
ff cliitAall - s)n ds
tn stn L' cl ds= (): + (clittaje - 1).
Then the components in (F f
dt is lower bounded by (elArtdyle - 1) dl. By
r'mn-1 [A++A,) (elActhy)t - 1) dt and upper bounded by JT (Art2,)
the celebrating approximation of incomplete gamma function when T is large, we have
Je
p4p-1 (Ae (g))
(clnttiie-) de ~0 (2+
TT
(cants)) -
Followed by
VT, tr orforf L. /BB -((((()((]]] al).
we can obtain that V7 = 7" C(r,T,11 TT,,,"....... Am).
This result leads to the fact that part 2 is
(C&(A1,"" ... Am 7, 7) + Co(A1, ... Am y, T)h o 0²22T + (Cio(A1, ... ,m 7, T)n?
+CI1 ..m= 7, T)h")"))))))))) o 04,T" + Cia(A1, Am, Tmo"""""" O(h"),
which coincides with the Var(hA; in the infinite-horizer discounted scalar case. The results in (3)
then follows.
E TRADE-OFF IN LQR WITH DENSE DIAGONALIZABLE MATRICES
T=2, B=16384
T=20, B= 32768, y 0.95
(Vhhh) Vi2
(Vm(h) V)²
10-1
101
A1
10-2
A2
A3
A3
M
100
AA
10-1
10-2
10-1
10"
10
10
10 1
10a
3, finite horizon
(b) infinite horizon
Figure 4: Mean-squared error trade-off in LQR with random symmetric diagonalizable drift matrices A. The matrices Af A,1,2,3,4.55 in each plot were generated by randomly sampling an eigendecom- position and then using it to compute the drift matrix A. The eigenvalues are uniformly sampled on bounded disjoint intervals and the cigenvectors are sampled randomly from the classical compact groups detailed in Mezzadri (2006). Note the matrices in (a) and (b) not equal.
Recall that in Fig. 1(b) and Fig. I(c), the drift matrices were scaled identity matrices. In this section, show empirically that the trade-off persists when A is dense, stable matrix which aligns with our theoretical results Theorem and Corollary 4. Fig. 4 clearly shows a trade-off for 10 randomly sampled 3 3 dense, stable matrices. The procedure for randomly sampling systems starts with uniformly sampling two eigenvalues from disjoint, bounded intervals, A E [-1.5, -1.0) and Aa (-1.0, -0.55). The final eigenvalue is set be X2 -1.0. Note that since all the
26

---

Under review as a conference paper at ICLR 2023
eigenvalues sampled are negative, any matrix whose cigenvalues are λ1 A2, Ag is said to be stable. Next, we randomly sample an orthogonal matrix Q using built-in ScIPY (Virtanen et al., 2020) routine, ORTHO GROUP.RVS. Now let A diag(A1. A2, Ag), the random, dense, stable matrix A is defined as = Q AQ.
F EXPERIMENTAL DETAILS
We summarize the environment--peccfie parameters in Table for the nonlinear-system experiments.
Table 1:
The setup of the environments. *: In MuloCo environments in OpenAl Gym, & timestep * frame_skip. öt = 0.001 seconds for the proxies to the continuous-time environments. Note that 'timestep" (the step size of the MuJoCo dynamics simulation) and 'frame_skip (the algo- rithmic step size) are two quantities in the implementation OpenAl Gym MuJoCo environments.
Environment
Episode Length
Original*
Horizon T (seconds)
(steps)
Pendulum
200
0.05
10
BipedalWalker
500
0.05
InvertedDoublcPendulle
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.04, 0.1]
BipedalWalker
10k
[0.001, 0.002, 0.104, 0.04,
InvertedDDoulleeendduuum
25k
1]
Pusher
25k
[0.002, 0,1,0,00000,,022,00,,0,,,,,,,,,, 0.4,
Swimmer
20k
[0.002,
0.0,0,000
Hopper
8k
[0.001, 0.002, 0.004, 0.000,0 0.1]
HalfCheetah
25k
0,0,
Ant
25k
[0.002, 0.1,4,00
0.02, 0.04,
27


Reviews:
[{"review_id": "dhQ2UdzQJy", "reviewer": "Reviewer_pVUY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the how discretization over the time horizon affect the error of LQR value estimation compared with the true continuous-time LQR value. The main result is about the mean squared error (MSE) of the Monte-Carlo policy evaluation, which reveals a trade-off between discretization time interval $h$ and the number of trajectories $M$. When the budget of total sample points is fixed, one can use this bound to find the optimal discretization time interval $h$ to minimize the MSE. Lastly, the authors use numerical simulations to demonstrate their theoretical findings in both LQR settings and nonlinear settings.", "summary_of_the_review": "This paper studies a relatively restrictive problem setting, and it is unclear whether the results or the proof techniques here apply to more general settings. Besides, I feel the technical contributions are not significant enough, and the numerical simulations are not sufficient to verify the theoretical findings quantitatively. Therefore, I recommend for reject.", "strength_and_weaknesses": "Strength:\n\nThis paper has a very good motivation to study the impact of discretization for general value estimation in reinforcement learning (RL) and optimal control. The main theoretical results are presented clearly with the discussion of their implications.\n\nWeakness:\n\n1.  It is hard to see the broader impact of this work. The problem setting seems to be restrictive: The results in this work only applies time-invariant LQR system, state-feedback controllers, and a specific form of disturbances. To address this concern, I encourage the authors to be more specific about what the “implications” are for more general settings. For example, if one wants to optimize the policy to minimize the continuous-time objective, how should the temporal discretization be chosen? Do the optimal temporal discretization depend on the current policy?\n2. The discussion about the technical difficulty for deriving the main result is not sufficient in the main body. As the authors discussed below Corollary 1, the error terms can be understood as a Riemann sum approximation error and the variance term. Before this work, are there existing results that bound Riemann sum approximation error? I believe this is important to clarify, because I feel bounding the variance term (It is usually called the stochastic error in RL literature) via independent trials is a standard technique.\n3. For the numerical simulations, I recommend the authors to do a more careful comparison with the theoretical optimal temporal discretization $h$, because I feel the trend of bias-variance trade-off can be expected even without the theoretical analysis in this work. It is more important to see how well the actual optimal $h$ matches the theoretical prediction $h^*(B)$.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bznt8wIPfXR", "reviewer": "Reviewer_UU8T", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "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. ", "summary_of_the_review": "Overall I think this is an interesting paper, which shows a trade-off for time discretization choice, which could be a potentially important guidance for practical usage. ", "strength_and_weaknesses": "**Strength**\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\n\n**Weakness & Questions**\n\n- For the non-linear case, why you choose a very short horizon. What happens if you choose $T=1000$ which is default in mujoco, and $\\gamma = 0.001$ ? Will you get similar results here? \n\n- For practise usage, it seems that we still don't know how to choose the optimal time discretization. Do you have any guidance or idea how to choose that in practise? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4xlUYlRk7X8", "reviewer": "Reviewer_GwC4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of approximating a continuous system from discrete measurements with a finite data budget. They first consider the simplest and canonical case of Monte-Carlo value estimation in a Langevin dynamical system with quadratic instantaneous costs. They obtain analytical expressions of the least-squares error that exactly characterize the approximation-estimation trade-off with respect to the step-size parameter. Second, they present a numerical study that illustrates and confirms the trade-off in both linear and non-linear systems, including several MuJoCo control environments. The findings imply that practitioners should pay attention to carefully choosing the step-size parameter of the estimation to obtain the most accurate results possible.", "summary_of_the_review": "Additional Problems: \n\nThe problem considered in this paper is closely related to stochastic differential equations. Specifically, using discrete measurements to approximate SDEs is similar to using the numerical solution to solve SDEs (for example, Euler-Maruyama method). What is the difference between your findings and those traditional results in numerical SDE?\n\nThe theoretical results seem to be restricted to the linear case, can authors make more discussions on the difficulty of extending results to nonlinear cases?\n", "strength_and_weaknesses": "Strengths:\n1. \tThe problem considered in this paper is important, and the results provide insights for practitioners on how to choose suitable stepsize for approximating continuous systems with discrete measurements.\n2. \tThe linear system considered in this paper is typical, and the theoretical results are rich and complete, with a clear explanation.\n3. \tThe numerical results match the theory well.\n \nWeaknesses\n1. \tCorollary 2 calculates the optimal step size using a Taylor expansion and omits high-order terms w.r.t. $h$. However, such estimation is only correct when $h$ is small, and the approximation error of $h^{*}$ is not given in Corollary 2. Therefore, we do not know whether the estimation is good and precise enough.\n2. \tIn the numerical experiments, the author considered a three-dimensional linear system. However, they only consider several special cases where $A=cI$, which is too special and too similar to the 1-D case. I think considering more general cases will provide more insights for the high-dimensional case. For example, $A=\\diag\\{c_1, c_2, c_3\\}$ where $c_1>c_2>c_3$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject