Maximizing the Value of Predictions in Control: Accuracy Is Not Enough
Authors: Yiheng Lin
Christopher Yeh
Zaiwei Chen
Adam Wierman
Venue: NeurIPS 2025 poster ()
Keywords: online control
predictions
linear quadratic regulator
model predictive control
Primary area: theory
TL;DR: We study the value of stochastic predictions in online optimal control with random disturbances.

Abstract: We study the value of stochastic predictions in online optimal control with random disturbances. Prior work provides performance guarantees based on prediction error but ignores the stochastic dependence between predictions and disturbances. We introduce a general framework modeling their joint distribution and define "prediction power" as the control cost improvement from the optimal use of predictions compared to ignoring the predictions. In the time-varying Linear Quadratic Regulator (LQR) setting, we derive a closed-form expression for prediction power and discuss its mismatch with prediction accuracy and connection with online policy optimization. To extend beyond LQR, we study general dynamics and costs. We establish a lower bound on prediction power under two sufficient conditions that generalize the properties of the LQR setting, characterizing the fundamental benefit of incorporating stochastic predictions. We apply this lower bound to non-quadratic costs and show that even weakly dependent predictions yield significant performance gains.

Maximizing the Value of Predictions in Control: Accuracy Is Not Enough
Yiheng Lin
Christopher Yeh
California Institute of Technology Pasadena, CA, USA yiheng tiiennl@caatecch.oo edu
California Institute of Technology
Pasadena, CA, USA cyeh@caltech.eet edu
Zaiwei Chen Purdue University West Lafayette, IN, USA chen52520purdue. edu
Adam Wierman
California Institute Technology
Pasadena, CA, USA
adamv@caltech.co
Abstract
We study the value of stochastic predictions online optimal control with random disturbances. Prior work provides performance guarantees based prediction error but ignores the stochastic dependence between predictions and disturbances. We introduce general framework modeling their joint distribution and define "prediction power" as the control cost improvement from the optimal use of predic- tions compared to ignoring the predictions. In the time-varying Linear Quadratic Regulator (LQR) setting, we derive closed-form expression for prediction power and discuss its mismatch with prediction accuracy and connection with online policy optimization. To extend beyond LQR, we study general dynamics and costs. We establish a lower bound on prediction power under two sufficient conditions that generalize the properties of the LQR setting, characterizing the fundamental benefit of incorporating stochastic predictions. We apply this lower bound non- quadratic costs and show that even weakly dependent predictions yield significant performance gains.
Introduction
Understanding the benefits of predictions in control has received significant attention recently [1, 3, 4, 5J. In this work, we study a class of discrete-time online optimal control problems in general time-varying systems, where random disturbances W, affect state transitions. The agent leverages prediction vector containing information about future disturbances to minimize the expected total cost over finite horizon T. To study the impact of using predictions, fundamental question is how to model disturbances and their relationship predictions. Prior works adopt different modeling approaches [1, 5, 6), each with distinct strengths and limitations.
common paradigm assumes perfect predictions over finite horizon k. yielding an elegant charac- terization of "prediction power" that improves with larger Under this model, predictions exactly reveal future disturbances W....., W [1] shows how prediction power grows with k in the LQR setting, and subsequent work extends this result time-varying systems [3]. As a result, the marginal benefit of one additional prediction decays exponentially with k offering insight into how select However, longer-horizer predictions are more costly and less accurate, and real-world predictions are rarely perfect [7], making this idealized setting challenging in practice.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

A natural extension of accurate predictions is to consider bounded prediction errors, which better captures practical challenges. Specifically, prediction errors measure the distance between the predicted and actual disturbances, and the resulting cost bounds depend on these errors [2, 5, 4]. This extension recovers the perfect predictions setting when errors shrink to zero. However, it can be overly pessimistic because, for any predictor, the same performance bound must also apply to an adversary that generates the worst prediction sequence to penalize the predictive policy subject to the same error bound. It overlooks stochastic dependencies between predictions and disturbances that can be valuable for improving control costs.
In this work, we propose a general stochastic model that captures the distributional dependencies between predictions and disturbances, without restricting prediction targets. horizon length, or requiring strict eπror bounds. Compared with previous stochastic methods [6, 8]. our approach further relaxes problem-specific assumptions and directly focuses on the incremental benefit of predictions. Such benefits can be subtle-often overlooked by classical metrics like regret or competitive ratio. To capture them, we define prediction power as the improvement expected total cost when predictions are fully exploited, which builds on and generalizes the notion from [1]. Our framework thus characterizes when and why predictions significantly boost online control performance.
Contributions. We introduce general stochastic model (Definition 2.1) that describes how distur- bances relate to all candidate predictors. We then define prediction power (Definition 2.4) which quantifies the incremental control-cost improvement gained by fully leveraging these predictions. To illustrate this concept, we derive an exact expression for prediction power in the benchmark setting of time-varying linear quadratic regulator (LQR) control (Theorem 3.2). Using this closed-form formula, we provide examples (e.g., Example 3.3) that illustrate why analyzing prediction accuracy is insufficient- saufficiettiimprovinng prediction accuracy may not always improve prediction power. Finally, we demonstrate the connection between prediction power and online policy optimization (Example 3.4), highlighting how practical algorithms can attain (a portion of) the maximum potential.
We extend our analysis of prediction power beyond the LQR setting. This generalization poses significant challenges due to the lack of closed-form expressions for the optimal policy. Building on insights from the LQR analysis, we identify two key structural conditions: quadratic growth condition on the optimal Q-function (Condition 4.1) and a positive semi-definite covariance condition on the optimal policy's s actions (Condition 4.2). These conditions are sufficient to derive a general lower bound on prediction power, formalized in Theorem 4.3. We apply this result to the setting of time-varying linear dynamies with non- quadraariiic cost functions. Under assumptions on costs and on the joint distribution of predictions and disturbances, we establish a lower bound on prediction power (Theorem 4.8), demonstrating that even weak predictions can yield strict performance gains.
Related Literature. Our work is closely related to the line of works on using predictions in online control. Our prediction power is inspired by [1], which defines the prediction power as the maximum control cost improvement enabled by k steps of accurate predictions in the time- inverinnti LQR setting, Compared with [1]. we extend the notion of prediction power to allow general dependencies between predictions and disturbances, and we consider more general dynamics/costs (Section 4). Rather than focusing on the prediction power, many works study the power of a certain policy class such as MPC [2, 3, 5, 4], Averaging Fixed Horizon Control [6, 8). Receding Horizon Gradient Descent [9, 10], and others [11]. While one can say the power of (generalized) MPC equals the prediction power in the LQR setting [1] (Section 3), they are not the same in general (see Appendix C.2).
Our work is, in part, motivated by both empirical and theoretical findings in the foccusd learning (DFL) (also referred to as
literature that prediction models with the same prediction accuracy may have very different control costs (see [12] for a recent survey). Research on DFL typically considers predictions given as point estimates of some uncertain input to decision-make
modeled as optimization problems, such as stochastic optimization [13], linear programs [14], or model predictive control [15], although more recent works have started exploring other forms of predictions such as prediction sets [16, 17]. In contrast, our work does not require any particular form of decision maker; instead, our main result characterizes the benefit of optimally leveraging predictions, for whatever form an optimal controller may take. Whereas DFL aims to design procedures for training prediction models that reduce downstream control costs, our work studies a more fundamental question about how much performance gain is achievable with better predictions. Another major difference between our work and typical DFL literature is that our controller must decide control actions sequentially in a dynamical system, where the predictions are
2

---

revealed in an online process. The controller can also build its knowledge from past disturbances and predictions infer future disturbances or the optimal control action. Thus, our online setting presents unique challenges compared with making one-shot decision for a classic optimization problem.
2 Problem Setting
We consider a finite-horizon discrete-time optimal control problem with time-varying dynamies and cost functions, where state transitions are subject to random disturbances:
Control dynamics: X St (X,, U2: W,), < T, with the initial state X,- = Io::
Stage cost: (X,, 0 S 1 < T, and terminal cost: (XT)
At each time step f, we X2 denote the system state and U, denote the control action chosen by an agent. The function ft R" x R. x R - IK" defines how the next state X depends on the current state X,, the control action Uz, and the random disturbance W,. The agent incurs stage cost he(X,,U; at each time step ( < ' and terminal cost /t (XT) at the final time step T. At each time step i, the controller observes the past disturbance Wt-1 and (possibly random) prediction vector Vi(0) Rd before selecting control action U., where 0 is parameter of the predictor generating the prediction. We formally define the concept of predictions and the parameter in the following.
Definition 2.1 (Predictions). At each time step L, the predictor with parameter 0 E O provides prediction (0). where è denotes the set of all possible predictor parameters. The predictions (V): and the disturbances Wo:T-1 live the same probability space.
We do not require the prediction Vi(@) to have any specific form as function of 9. The parameter O primarily used for distinguishing different predictor candidates.
Compared with previous works [3, 18] that assume predictions targeting specific disturbances, Definition 2.1 focuses the stochastic relationship between predictions and system uncertainties, yielding a unified framework for comparing different forms of prediction based on their effectiveness for control even if their precise nature is unknown. Because predictions and disturbances share the same probability space, we can compare prediction sequences (0) and Vo')- generated by different predictors with parameters 0 and 0'.
Observe that the disturbances Wor-1 and predictions Definition 2.1 do not depend on the current state or past trajectory, reflecting their exogenous nature. For example, consider the problem of quadcopter control in windy conditions [19]. In this case, the wind disturbances are not influenced by the quadcopter's 's state control inputs. Under this causal relationship, we define the problem instance as = (Wor-1, (Vo.r (0) Joee), and make the following assumption.
Assumption 2.2. The problem instance before the control process starts, i.e., it will not be affected by the controller's 's states/actions.
sampled from the distribution of problem instances
Let = (wo:r-1, (1o:r-10)))e) (0))) denote a realization of the problem instance, including distur- bances and all parameterized predictions. Under Assumption 2.2, = is viewed as realized to E before control begins, although the agent observes each disturbance and prediction step by step. Similar assumptions about oblivious environments or predictions appear in online optimization [20, 21], ensuring that future disturbances or predictions will not be affected by past states or actions. Hence, for a fixed predictor parameter 8 we define predictive policy as a mapping from the current state and past disturbances and predictions to a control action.
Definition 2.3 (Predictive policy). Consider a fixed predictor parameter O. For each time step t, ler (0) == (Wo.e-1, (0)) denote the history of past disturbances and predictions, and let F.(0) (0)) A predictive policy that applies to the predictor with parameter 0 a sequence of functions To.T where ne maps a state/history pair to a control action.
= for predictor parameter 8, we evaluate its performance via the expected total cost over E: J (+) = E E hx, U.) + (xr)) where X₂ = Zo. X++1 = (X,, Uz Wt), U, n, (X:: (0)). for t = O...., T - 1. The optimal cost under is defined as (d) = min, (0), where the minimum is over all predictive policies that use the predictor parameter 0.
Given a fixed predictive policy sequence
For any random variable Y, (YY denote the o-aggebra it generates.
3

---

Following [1], we define prediction power by comparing against baseline that provides minimal information (e.g., no prediction). Without loss of generality, let 0 E θ be the baseline predictor parameter so that any 0 & O provides at least as much information as 0, i.e., F.(0) 2 F()).. Based on this baseline, we define prediction power as the maximum possible cost improvement achieved by using predictions under & relative to the baseline, formally stated in Definition 2.4.
Definition 2.4 (Prediction power). For a predictor with parameter 0, its prediction power in the optimal control problem (1) is P(0) == (0) (0)-
Our definition of prediction power is based on the optimal control policy under a given predictor parameter and, therefore, is independent of any specific policy class. Many previous works have considered prediction-enabled improvement within a specific policy class [9. 10, 6], where they focus on changes in J (0) rather than J (0). In other works, policies include parameters that can be tuned to perform optimally under a specific predictor; that is, min policy class J (0). While these approaches are useful in specific application scenarios, our definition, based on the general optimal policy, is more universal because: (1) imposing policy class constraints may lead to performance loss, and (2) the extent of improvement can depend on policy design and parameterization, which shifts the focus away from valuing predictions themselves.
When the baseline predictor O is no prediction, the prediction power is guaranteed to be non-negative. This is because the optimal policy for the no-prediction case is also predictive policy when predictions are available, i.e., the controller can simply ignore the predictions. But the prediction power could be zero, for example, when the predictions are independent of the disturbances. Further, the prediction power does not increase if one replaces the original prediction (0) by any function of the history (0), because this additional step cannot increase the information available at time step t.
Throughout this paper, we use गं = #0.7-1 and x² - to denote the optimal policy for the predictor with parameter and 0. respectively. In other words, J (0) = (0) and J* (0) (0). To compare the policies n² and æ. we introduce the instance-dependent Q function, inspired by the Q function in the study of Markov decision processes (MDPs). For a given state-action pair (zz u) and Q function for a policy evaluates the remaining cost
problem instance ç, the instance-dependes incurred by taking action u from state x and then following policy π for all future time steps. Recall that the history I=(6) contains all past disturbances and predictions that are observed until time step T. Using e (0) to denote the realization of (0), the instance-dependent Q function is defined as
Qf (xx, (x = EZ=
T-1 (x u.) + (r(rr), where Ie xx U4 U.
(2)
subject to the constraints that = (x,, uriwy) for t S S < T and u, = ( (0) for t < T < T. Recall that & is the realization of problem instance 3\t that contains all disturbances and predictions for all time steps. Thus, the disturbance w- and the history (0) in (2) are decided by the problem instance É. which is an input to Q Similarly, we define Q (z, u; {) by replacing 0 with O and T" with से in (2). Importantly, our instance- deeendend Q function is different from the classical definition of the Q function for MDPs reinforcement learning (RL), where it is the expectation of the cost to go. The gestance-dependers Q function denotes the actual remaining cost, which is messurral random variable. The classic definition of the Q function can be recovered by taking the conditional expectation, i.e., E QT" (I, u; 3) (.(0)= - (0)) [()))= It is worth noting that our instance-dependent Q function is about the cost instead of the reward, so lower values are better.
=
With this definition of the pustance-dependee Q function, the policies से and dO can be expressed as recursively minimizing the corresponding expected Q functions conditioned on the available history. Starting with Cg (x: {) = hr()), for time step t = T - 1,...,0., O, we have
Q²" (a., () == h4 (z. u) + Caa (fe( u; E)) for x E TR.", u E R. and problem instance ; m (1) = arg min E [ (I, (3) (,(0) = (.()) -0]0)]]
for x E IR" and history (=));
oF (x; = Q:" (z, T. (a: 4 (+)): {), for E I2" and problem instance &.
Similar recursive relationships also define the optimal policy मे for the baseline predictions, and we only need to replace with and TO with ग in the above equations. The recursive equations in (3) can be viewed as generalization of the classical Bellman optimality equation for general MDPs

---

P Pr. And the 3 LTV Dynamics with Quadratic Costs
We first characterize the prediction power (Definition 2.4) linear time-varying (LTV) dynamical system with quadratic costs, where the dynamics and costs are given by:
Control dynamies: X A,X; + B,U, + Wi, for 0 5t
stage cost: X, Q, + U, R,U, for 0 Σ < T; and terminal cost: P;
(4)
where Q0:T-1, Ro:T-1, and PT symmetric positive definite. The classic linear quadratic regulator (LQR) problem, along with its time-varying variant that we consider, has been used widely as a benchmark setting in the soaminngfor-contro) literature. It also serves good approximation of nonlinea systems near equilibrium points, making it amenable to standard analytical tools. We begin by defining key quantities that will be useful for stating the main results in this section. For t= T 1,...,0, O, we define the matrices Hr, Pt, and Kr recursively according to
H. = Re + B. P.+. Bt) BB, P. = Q: + A Pe+1 A Pe+1 H. A,, and K; (R, + P. Pt)
(5)
Moreover, we define the transition matrix 4 Pia,t1 Piz,11 if 1/2 S t, and
P12.11 = (Atg-1 Btg- ( B1g 2 22) ... (Ar, Br, Kt,), if 12 > 41
(6)
The matrix K2 is the feedback gain matrix in the optimal policy, and P: is the matrix that defines the quadratic term in the optimal cost-to-go function. To simplify notation, we define the shorthands 1 T/K IE [W, , [e))] and wh1 = E [W, (+) = ((0)..
Proposition 3.1. In the case of LTV dynamics with quadratic costs, the conditional expectation of the optimal function QT (x,, u; 1.(0) = =e(0] can be expressed as
(u (u+ K, (1)( (R₃ + B.T Pc+1 B,) (u + KGY ut ((((())) + 1/p"" (x; L())),
where vit" (x; (0)) is function of the state and the history (0) that does not depend the control action u. Here, it (v+(0) = (R, + B, Pr+ - Σx= TT
optimal policy can be expressed as n (z; (0) - K, + ui (L)).
We derive the closed-form expressions in Proposition 3.1 by induction following the backward recursive equations in (3); the full proof is deferred to Appendix A.I. With these expressions, obtain a closed-form expression of the prediction power. We defer its proof to Appendix A.2.
Theorem 3.2. In the case of LTV dynamics with quadratic costs, the prediction power of the predictor with parameter 0 P(O)= = - Th-( (RR + B, P.)IB [Cov [u]] (T)( [O]]]
While the optimal policy in Proposition 3.1 is restricted to the LQR case, we can interpret the optimal policy as planning according to the conditional expectation following the idea of model predictive control (MPC) [1]. which is casier to generalize. The agent needs to solve an optimization problem and re- ee-plan at every time step. At time step f, the agent solves
arg min
E ET= h (X,, u.) (x()T) 1((0) = (n())
(())
subject to the constraints that X,+1 f+(X,, ur; W-) for 2 and X, Then, the agent commits to the first entry Welt of the optimal solution Tp (x; (0)). In the LQR setting, we can further simplify it be planning according w p i.e.,
T-1
arg min Me-T-1
h- h-(a,, ur) + hT(xT) Σ T-t
(8)
subject to the constraints that 2,+1 fr (IT, Uyj wp)) for 2 and σ, We defer detailed discussion and proof to Appendix A.3.
The MPC forms of the optimal policy (7) extends the result in [1], which shows that MPC is the optimal predictive policy under the accurate prediction model in time-invariant LQR. When
5

---

the predictions are inaccurate, and the system is time-varying. MPC is still optimal if we solve the predictive optimal control problem in expectation (7).
Evaluation. One can follow the expressions in Theorem 3.2 to evaluate the prediction power, but it requires taking the conditional covariance the top of conditional expectations (7.) (1e (0)) in Proposition 3.1). To avoid this recursive structure, an alternative way is to first construct the surrogate optimal action which defined as
प (=) == - (Re + B, Pt+ E. 1
We call (E) the surrogate-optimal action, because is the optimal action that an agent should take with the oracle knowledge of all future disturbances at time t. The prediction power in Theorem 3.2 can be expressed as E [Cov | (E) [[))]]] [Cov iu (E) I(()]]] Following this decomposition, we propose an evaluation approach that constructs uy (=) before estimating its conditional covariance with respect to I (0) and (0) separately. We defer the details to Appendix A.4.
3.1 Prediction Power Accuracy
As Proposition 3.1 suggests, one way to implement the optimal policy is to predict each of the future disturbances WiT-I and generate the estimations w ((:T-1)] (i.e., the conditional expectation of future disturbances given the history (0) at time step t) in deciding the action at time step t. However, two controllers with the same estimation error (as measured by mean squared error (MSE)) can have very different control costs. Because of this reason, the control cost bounds depend on the estimation errors in previous works [5, 2, 4] must be loose, one cannot rely them infer or compare the values of different predictors.
To illustrate this point, we provide an example where the prediction power can change significantly when the prediction accuracy does not change.
Example 3.3. Consider the time-imariant LQR setting, i.e., assume A₁ = A, = B. Q.
Q, R. for all t and P1 = P the solution to the Discrete-time Riceati Equation (DARE) in (4). Suppose the disturbance is sampled We (0, at every time step t, where use the notation 1 to denote the identity matrix. Let p E [0, 222 be a fixed coefficient. We construct a class of predictors from the disturbances } by applying the affine transformation V.(0)= = p&W, + ex (p, 0) for 0 E 2R222 that satisfies A0 = IT. where the random noise (t 0) is independently sampled from Gaussian distribution N I p0200
We can construct 0 such that (0) and Vi(TT) achieve the same mean-squar error (MSE) when predicting each individual entry of W, yer P(0) > P(T).. To construct 0, note that (W₂, (O)) satisfies E [We V=(0)] p0 V and Cov [We V+(0)] = 1=p220 0. Thus, we can change O without affecting the MSE of predicting each individual entry as long as the diagonal entries of 9 a remain the same. However, by Theorem 3.2, we know the prediction power is equal to p²T Tri6 . OPHP), where H B(R+ BT PB) Thus, the off-diagonal entries o 0 can also affect the value O OPHP). We instantiate this example with a 2-D couble-integraan dynamical system in Appendix 1.5.1: the predictors with parameters I and O share the same MSE but their prediction powers are significantly different.
Example 3.3 shows how prediction power can vary even when the accuracy of predicting each entry of the disturbance W, remains the same, where the construction leverages the covariance between the predictions for different entries of W. While the construction in Example 3.3 requires n > we also provide an example with = 1 and multiple steps of predictions in Appendix A.5. From these examples, it is clear that one should not use the MSEs of predicting future disturbances to infer the prediction power. The intuition behind Example 3.3 does not require very specific choice of the function ()): The underlying idea is that the MSES of estimating each individual entry of the multi-dimennional disturbance W, are insufficient to decide the prediction power. The off-diagonal entries of the covariance matrix Cov WW, Vo)) also matter, and their impact on the prediction power depends on the dynamics (A, B, Q, R). Therefore, general accuracy metric (like MSE) that is unaware of (A, B, Q. R) can be misaligned with the prediction power. The mismatch also relates to the findings in the decision- focused learning literature discussed in the related work section.
'The simulation code for all examples (Examples 3.3, 3.4, and A.2) can be found at https: : //gi wtt.ghitub.coo..... sthhenglinS7//Predic.... Power.

---

1.50
2.5
Avennge cini improwement against
1:25
Average cost impRoveriant against
2.0
1.00
1.5
0.25
0.25
0.5-
0.00
Prediction (1))T
Prediction power (P(2)/7)
-0.55
M-GAPS
Optimal prodictive policy (ml)
0.0
M-GAPS
Optinal predictive policy
0.20
20000
80000
60000
sodon
20000
40000
60000
80000
Time step
Time
Figure 1: Example 3.4: Prediction (1)1 avail- able. Candidate policy: uy Kr (1).
Figure 2: Example 3.4: Prediction (2( is avail- able. Candidate policy: un - -xx + (2).
3.2 Prediction Power and Online Policy Optimization
The closed-form expression of the prediction power, presented in Theorem 3.2, characterizes the maximum potential of using given prediction sequence (0). Here, we draw connection between prediction power and online policy optimization [22, 23], which aims to learn and adapt the optimal control policy within certain policy class over time: prediction power serves as an improvement upper bound of applying online policy optimization to predictive policies, although it is generally unattainable. In the following example, we demonstrate this bound using M-GAPS [24], state-of-the-art online policy optimization algorithm.
scenarios under the the prediction is (1) == pW, + pp, ), we let M-GAPS adapt within the candidate policy class ur -x, (1), where Y, R1x2 is the policy parameter." Here, the optimal predictive policy x² is contained in the candidate policy class. We plot the average cost improvement of M-GAPS and X| compared against the optimal no-p no-prediction policy ă in Figure 1. From the initialization To 0, M-GAPP tunes Y, to improve the average cost over time, and the average cost improvement against converges towards the averaged prediction power P(1)/T.
Example 3.4.
We construct
setting Example 3.3. First, when
In the second scenario, we change the prediction to apply M-GAPS to Vi(2) = V141(1) (i.e., the same prediction before is made available 1-step ahead). We let M-GAPS adapt within the same candidate policy class u, = =- -K + UU, where the policy parameter is still Y, E RIx2 Unlike the first scenario, the optimal predictive policy n² is not contained in the candidate policy class, because x²2 uses both (2( and (2) to decide the action. As result, M-GAPS cannot achieve an improvement that is close to the averaged prediction power (22)/T, which achievable by x² (see Figure? 2).
The details of Example 3.4 are provided in Appendix A.6. It demonstrates how prediction power serves as an upper bound for the cost improvement achieved by online policy optimization. Conversely, online policy optimization offers practical tools to achieve (part of) the potential benefit of using predictions without requiring explicit knowledge or estimation of the joint distribution between predictions and true disturbances.
4 Characterizing Prediction Power: A General-Purpose Theorem
In this section, provide theorem to characterize the prediction power P(0) within the general problem setting introduced in Section 2. Our result relies on two conditions about growth property of the expected Q function under n" and the covariance of the optimal policy's is action when conditioned on the o-algebra F, (0) the baseline, We state these conditions and provide intuitive explanations.
'Intuitively, M- M-GAPS works by taking the gradient of cost function with respect to policy parameters at every time step, and it takes gradient steps to update Y,, allowing to converge towards the optimal policy parameters. Our goal is to highlight the connection between prediction power and online policy optimization, so the specific online policy optimization algorithms and their proofs not the primary focus here.
7

---

Condition 4.1. For sequence of positive semi-definie matrices Mo.r-1. the following inequality holds for all time steps S t < T: For any z E R", R,, and history (0))
E OF (x, w; oJ (x: E) T. (0) = (0) ž (u -,; (((],((())) M,(" - (z; (10)
The LQR setting (Section 3) satisfies Condition 4.1 with M, = RS + B, Pi+1 Bt. But Condition 4.1 is applicable beyond the LQR setting. For example, show it holds under non-quadratic cost functions in Section 4.1.
Condition 4.1 states that conditioned on any history 42 (f). the expected Q function of policy n² grows at least quadratically as the action u deviates from the optimal policy's action. Note that one can always pick M, to be the all-zeros matrix to make Condition 4.1 hold, but the choice of M, will affect the prediction power bound in Theorem 4.3. When M, > 0, deviating from the action of policy T" causes a non-negligible loss. The loss is characterized by the difference between the resulting Q function value and the cost-to-go function value. When this condition does not hold with any non-zero matrix M, one can construct an extreme case when QF" is a constant by letting all cost functions ho:r be constants; in this case, the prediction power must be zero because every policy achieves the same total cost no matter what predictions they use.
Condition 4.2. One of the following holds for the optimal policy x²:
(a) For positive semi-definize matrices Co.T-1, the following holds for all time steps 0 S t < T:
E [Covv [m] (x; | [.(O]]] ł Ex, for any F. mmemmuuuallll X.
(11)
(b) For nonnegative scalars -1 the following holds for all time steps Ost<T
E
(()) [(OO)))] 2 ot, for any m-)aasurlle X. Cov [ [Tr[Cov]]]]
(12)
Before diseussing the details, we note that by setting o; = (T((E,), Condition 4.2 (a) implies (and is therefore stronger than) Condition (b). Similar to Condition 4.1, one can always pick E, to be all-zeros matrix to satisfy Condition (a). but it will affect the prediction power bound. The LQR
setting (Section 3) satisfies Condition 4.2 (a) with Σ, = E [Cov [u.] (I+(O)) [[]]
Condition 4.2 (a) states that conditioned on the history (0) from the baseline, the covariance matrix of policy "s action from any (meauullrre state is positive semi-definite in expectation. Recall that (0) = o (4(()), To understand this, suppose that the agent only has access to the baseline information. Then, the agent cannot predict the action that policy x² would take. This should usually hold because the action n. (X; (0)) is not (O)))measurabee the mean- square prediction error cannot improve below a certain threshold. When this condition does not hold with non-zero matrix Σ, (or scalar a₂), one can design policy म' that always picks the same action as T but only requires access to the baseline information T, (O), which implies P(0) = 0 because (0) < J (0) = (0). This can happen, for example, when Wo.r -1 are deterministic.
and the lower bound in (11) implies
Note it is possible that the optimal action at different states has positive variance in different directions, but there is no non-trivial lower bound on the covariance matrix as required by Condition 4.2 (a). In this case, Condition 4.2 (b) provides weaker alternative and would be useful when can only establish a lower bound on the trace of the optimal action's 's covariance matrix (e.g., Section 4.1).
Theorem 4.3. If Conditions and 4.2 (a) hold with matrices Mo.T-1 and Eo.r-1, then P(0) 2 EID Tr. Alternatively, if Conditions 4.1 and 4.2 (b) hold with matrices Mo.T and scalars -1 then P(0)= N IT- (M;) To where Mmii (-) returns the smallest eigenvalue.
We defer the proof of Theorem 4.3 to Appendix B. As a remark, in the LQR setting, the first inequality in Theorem 4.3 holds with equality, and it recovers the same expression as Theorem 3.2 in Section 3. There are two main takeaways of Theorem 4.3. First, recall that one can always pick M, and Σ, to be the all-zeros matrices to satisfy Conditions 4.1 and 4.2. In this case, Theorem 4.3 states that P(0) 2 O. which means that having predictions, no matter how weak they are, does not hurt. Second, to characterize the improvement in having predictions, Conditions 4.1 and 4.2 can establish a lower bound for the prediction power that is strictly positive if Er,,, > 0 or /mmin (M.)o, >> 0. We provide an example to help illustrate how Conditions 4. and 4.2 (a) can work together to ensure that the predictions can lead to strict improvement on the control cost (see Figure 3 for an illustration).
8

---

5.0
E045_.00 u: [/-(00)
10, x)
1/- =
2.5
E EQ, (;
10-1(0) =1
0.0
-2
Figure 3: An illustration of why predictions are helpful, corresponding to Example 4.4. The expected functions with perfect predictions (green and orange lines) have lower minima than the expected Q function with uninformative predictions (blue line).
Example 4.4. Consider the following optimal control problem
Dynamies: X Ut + Wt, Stage cost: he(x, u) x², Terminal cost: hvr(s) =x²,
where each disturbance W. is sampled independently according to P(W, --1) - = 1) Suppose that the predictor with parameter 9 can predict We exactly (i.e., V,(0) = We). while the baseline predictor is uninformative (e.g.. VO( = O). The Q functions, cumulative cost, and optimal actions under each predictor are
OF (z, = x2 + +u+ Vi(0))
(, (u+ + +T - -
C (x: = 2²,
(x,E)) = 2² (T tt,,
(1; = - Vv(00) V=(0)==- -e
(1; 1(()) = 0.
The Q function QF" is strongly convex in u, with Condition 4.1 holding for any Mj E [0. 1]. Furthermore, the optimal action has positive variance, with Condition (a) holding for any E, E [0. 1]. Thus, by Theorem 4.3, the prediction power satisfies P(A) 2 T. Indeed, by comparing the cumulative cost functions, we see that the predictor with parameter incurs lower cumulative cost by exactly T (as expected by Theorem 3.2).
Figure 3 illustrates the expected Q functions time t T' 1nd O. which the policies D (x; (e)) and Te (z; (e))) seek to minimize. The expected Q functions with perfect predictions have lower minima than the expected function with uninformative predictions.
Theorem 4.3 provides useful tool characterize the prediction power by reducing the problem of comparing two policies n² and मे over the whole horizon to studying the properties of one policy x² at each time step. Our proof of Theorem 4.3 follows the same intuition the widely- rusedl-used performance difference lemma in RL (see Lemma 6.1 in [25]). but we adopt novel methods to compare the per-step "advantage" of n along the trajectory of π with the conditional covariance of policy T²'s actions. When only the baseline information is available, the agent must pick a suboptimal action (11) and incur loss (10) each step, which accumulates the total cost difference.
While Theorem 4.3 applies to the general dynamical system and cost functions in (l), the two conditions with their key coefficients M, and Σ, (or στ) still depend on the optimal Q function and the optimal policy that are implicitly defined through the recursive equations (3). To instantiate Theorem 4.3, we need to derive explicit expressions of M, and E, under more specific dynamics/costs.
4.1 LTV Dynamics with General Costs
In this section, consider online optimal control problem with linear time- timeivarying dynamics and more general cost functions compared with the LQR setting in Section 3.
Control dynamics: X = A,X, + B,U, + We, for 0 < <<<T T; stage cost: hū (Xx) + (U:), for 0 < T; and terminal cost: (XT).
(13)
The LTV system with quadratic cost functions studied Section 3 is a special case of (13). The setting is challenging because the optimal Q function/policy n² do not have closed-form expressions like Proposition 3. To tackle it, we follow the recursive equations (3) to establish Conditions 4.1 and 4.2 (b). We make the following assumptions about the cost functions and dynamical matrices:

---

Assumption 4.5. For every time step t, h is stronngyy convex and ---stooth, and hy is pu strongly convex and sm-sohth. The dynamical matrices satisfy PAT T 1 A A, 3 lA I and pBl 1 B. Br 3 fl.. Further, we assume l < and PB > O.
Under Assumption 4.5, we can verify Condition 4.1 and show that the expected cost-to-go functions are well-conditioned. We state this result in Lemma 4.6 and defer its proof to Appendix C.4.
Lemma 4.6. Under Assumption 4.5, Condition 4.1 holds with Me- pul. Further, conditional
expectation E E[C₁ (x; | Tx(()= (0) function of x. is pe-strongly convex and fm-smooth for any history (0), where μ4 and & are defined as follows: Let por = Pr and Er = lz.
Mule41
14 fz MA
MAA Pa + 6pp41
and & =bx + lA le+1, for time =T - -1,1 1.....0. O.
(14)
To show Lemma 4.6 and (14), we prove properties of infimal convolution (see (35) in Appendix C.I) to preserve strongly convexity, smoothness, and the covariance of the input functions or variables.
To establish the second condition about the covariance of the optimal policy's 's action, we make the following assumption about the joint distribution of the disturbances and the predictions:
Assumption 4.7. The disturbances and predictions can be grouped as pairs {(W,, VO))
where (We, (0) is joint Gaussian and independent of (We, v V0) when t + t'. Further, assume that the baseline is no prediction, i.e., Vz( = O. And for O E O, there exists (²( R20 such that
Cov [We] Cov [W, Vi(0)] ž (f), any S < T.
With Assumption 4.7 and Lemma 4.6, we can verify that Condition (b) holds with
n1:(0)pf41 HB
Tr Cov (1; F(OO] 2 o = 2(e + (+1v(8))
(15)
Since Conditions 4.1 and (b) hold, we apply Theorem 4.3 to obtain the prediction power bound. Theorem 4.8. In the case of LTV dynamics with well-conditioned costs, suppose Assumptions 4.5 and 4.7 hold. The prediction power of the predictor with parameter 0 is lower bounded by P(0) > Ei PuTt, where of is defined in (15).
We provide a more detailed proof outline and the proofs in Appendix C.I. As a remark, the lower bound of the prediction power in Theorem 4.8 shows that even weak predictions (i.e., small but non-zero (e) in Assumption 4.7) can help improve the control cost compared with the no- no-prediction baseline. Although Assumption 4.7 limits (i( to be only correlated with We, c, we provide a roadmap towards more general dependencies on all future W in Appendix E.
Concluding Remarks
In this work, we propose the metric of prediction power and characterize it in the time-varying LQR setting (Theorem 3.2). We extend our analysis to provide lower bound for the general setting (Theorem 4.3), which is helpful for establishing the incremental value of (weak) predictions beyond LQR (Theorem 4.8). We emphasize that our framework is very broad. For example, if we let the parameter represent the dataset that the predictor is trained on, then the prediction power P(0) effectively quantifies the value of that particular dataset with respect to the optimal control problem.
We would like to highlight three directions of research inspired by our results. First, while our work establishes prediction power of a predictor with parameter 0 relative to strictly dess-informatio baseline, it does not immediately enable comparison between two arbitrary parameters 0 and 0' when our general lower bounds in Section 4 are not tight. Second, while we discuss how to evaluate prediction power of given parameter 6, our work does not specify what the optimal is. The problem of learning the parameter that maximizes P(0) may be interesting future work. Third, a natural future direction to extend the current analysis to systems with partial observability. This remains challenging, as one must distinguish the disturbances in the system dynamics from the noises in the observation model, and the optimal policy's 's functional form becomes difficult to characterize due to its dependence the entire history of partial observations and predictions.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by NSF grants 2106403, NGSDI-2105648) and the Caltech Resnick Sustainability Institute.
CNS-2146814, CPS-2136197, CNS-
References
[1] Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman. The power of predictions in online control. Advances in Neural Information Processing Systems, 33:1994- 2004, 2020.
[2] Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Competitive control with delayed imperfect information. In 2022 American Control Conference (ACC), pages 2604-2610. IEEE, 2022.
[3] Yiheng Lin, Yang Hu, Guanya Shi, Haoyuan Sun, Guannan Qu, and Adam Wierman. Perturbation-based regret analysis of predictive control in linear time varying systems. Advances in Neural Information Processing Systems, 34:5174 178-5188, 2021.
[4] Yiheng Lin, Yang Hu, Guannan Qu, Tongxin Li, and Adam Wierman. Bounded-regret mpc via perturbation analysis: Prediction error, constraints, and nonlinearity. Advances Neural Information Processing Systems, 35:36174 771877777.711 2022
[5] Runyu Zhang, Yingying Li, and Na Li. On the regret analysis of online lqr control with predictions. In 202/ American Control Conference (ACC), pages 697-703. IEEE, 2021.
[6] Niangjun Chen, Anish Agarwal, Adam Wierman, Siddharth Barman, and Lachlan LH Andrew. Online convex optimization using predictions. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 191-204, 2015.
[7] Tianyu Chen, Yiheng Lin, Nicolas Christianson, Zahaib Akhtar, Sharath Dharmaji. Mohammad Hajiesmaili, Adam Wierman, and Ramesh Sitaraman. Soda: An adaptive bitrate controller for consistent high-quality video streaming. In Proceedings of the ACM SIGCOMM 2024 Conference, pages 613 644, 2024.
[8] Niangjun Chen, Joshua Comden, Zhenhua Liu, Anshul Gandhi, and Adam Wierman. Using predictions in online optimization: Looking forward with eye the past. ACM SIGMETRICS Performance Evaluation Review, 44(1):193-22) 2016.
[9] Yingying Li, Guannan Qu, and Na Li. Using predictions in online optimization with switching costs: A fast algorithm and fundamental limit. In 20/8 Annual American Control Conference (ACC), pages 1008-3013. IEEE, 2018.
[10] Yingying Li, Xin Chen, and Na Li. Online optimal control with linear dynamics and predictions: Algorithms and regret analysis. Advances in Neural Information Processing Systems, 32, 2019.
[11] Yiheng Lin, Gautam Goel, and Adam Wierman. Online optimization with predictions and non-convex losses. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1-32, 2020.
[12] Jayanta Mandi, James Kotary, Senne Berden, Maxime Mulamba, Victor Bucarey, Tias Guns, and Ferdinando Fioretto. Eecision-focusee learning: Foundations, state of the art. benchmark and future opportunities. Journal of Artificial Intelligence Research, 80:1623-1701, August 2024.
[13] Priya I.. Donti, Brandon Amos, and J. Zico Kolter. Task-based End-to-end Model Learning in Stochastic Optimization. In Advances in Neural Information Processing Systems, volume 30, Long Beach, CA, USA, December 2017. Curran Associates, Inc.
[14) Adam Elmachtoub and Paul Grigas. Smart "Prddict, then Optimize". Management Science, 68(1):9-26, January 2022.

---

[15] Brandon Amos, Ivan Jimenez, Jacob Sacks, Byron Boots, and J. Zico Kolter. Differentiable Planning and Control. In Advances in Neural Information Processing
MPC for Systems, volume 31. Curran Associates, Inc., 2018.
[16] Christopher Yeh, Nicolas Christianson, Alan Wu, Adam Wierman, and Yisong Yue. End-to-end conformal calibration for optimization under uncertainty. Preprint arXiv:2409.20334, 2024.
[17] Irina Wang, Cole Becker, Bart Van Parys, and Bartolomeo Stellato. Learning Decision-Focused Uncertainty Sets in Robust Optimization, July 2024.
[18] Tongxin Li, Ruixiao Yang. Guannan Qu, Guanya Shi, Chenkai Yu, Adam Wierman, and Steven Low. Robustness and consistency in linear quadratic control with untrusted predictions. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(1):1-35, 2022.
[19] Michael O'Connell, Guanya Shi, Xichen Shi, Kamyar Arizzadenesheli, Anima Anandkumar, Yisong Yue, and Soon-Jo Chung. Neural-fly enables rapid learning for agile flight in strong winds. Science Robotics, 7(66)eebb6657, 2022.
[20] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization,
[21] Daan Rutten, Nicolas Christianson, Debankur Mukherjee, and Adam Wierman. Smoothed online optimization with unreliable predictions. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):1-36, 2023.
[22] Yiheng Lin, James A. Preiss, Emile Timothy Anand, Yingying Li, Yisong Yue, and Adam Wierman. Online adaptive policy selection in time-varying systems: No-regret via contractive perturbations. In seveehy Conference on Neural Information Processing Systems, 2023.
[23] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference Machine Learning, pages 111-119. PMLR, 2019.
[24] Yiheng Lin, James A Preiss, Fengze Xie, Emile Anand, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online policy optimization in unknown nonlinear systems. In The Thirty Seventh Annual Conference on Learning Theory, pages 3475-3522. PMLR, 2024.
[25] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267- 274, 2002.
[26] Amir Beck. First-Order Methods in Optimization. SIAM, 2017.
[27] Jerrold E Marsden and Anthony Tromba. Vector Calculus. Macmillan, 2003.
12

---

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

---

Answer:
[Yes]
Justification:
All of our theoretical results are based on rigorous assumptions and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We describe the full problem settings and algorithm patameters in all simula- tions.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We submit the simulation code in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
Sibllie/guides/CdeSSubiiii boseodeeSsamssssooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. ccppp.ccpppulcc///eecccc/ wetpiiiiiggiee...eeeeo/eooeoeeee /CodeSubmia (isoiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all the details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We discuss why we believe each experiment observation is significant.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We discuss about compute resources for each simulation result.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips httpp//ss...ppppcccccccccceeeeee innes
Answer: [Yes]
Justification: We check the NeurIPS Code of Ethics and helieve our work conforms with every code.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work focuses on theoretical research of online control. We do not see any potential societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: We do not use any specific assets beyond standard open-source scientific Python packages such numpy and matplotlib for running experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Upon paper acceptance, we will release our code on GitHub with a permissive license. Our paper does not introduce any new data or models.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this work does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https:/ //ttrr//seu../eeeee Wwweuripsscc/ooofeeeee /LLMM for what should or should be described.
19

---

A Proofs and Examples for LTV Dynamics with Quadratic Costs
A.1 Proof of Proposition 3.1
Recall that we introduce the shorthand
W T/c = [W, (+())
We show by induction that
Qf (x, ux 4.(0)]
= (w+ K,E- (I,())) (R, - B, Pi) (u Kat (I(()())) + ot (o: (())), (z; ((0)) = KK (I)))..
together with the expression of the optimal cost-to-go function
T-1 Σ
)
T
CT
(x: 3) T((O)] T Pex +2
To
+ v.(T((0)), T+1 P W W/ 7/2
(16)
where recall that for 1s > t1,
T 12,41 = (Ai, - B1, Kt,) ... (At,11
=AA -A,, P ... (A Atg-1Po
and V, (I)( a function of the history observations/preciitioss which does not depend on z. Note that (16) holds when = 7 hecause CT (x; = x. T Pr..
Suppose that (16) holds for t + 1. Then, we have
E
(xr + W;: T.) C
E
E C (xr + W); le+ (0)] 1.(00]
=E
(x [(x
W.) Pe+i (x + Wo) 1.(00]
+ 2E
Σ
r P We
7/++1 I:(0)
r=141
(E
T-1
+ +2E 2E
Σ
T
W
r|e+1
W, 1(())
+E +B[M [())
r=t+1
T
T-1
x P2410 +2
Po
Σ r=t+1
x PrttsPti
x Tr(PP++1 Cov (W, 4(0)))
+ 2IE
Σ
T 2 W W 7((+1)
Wi 1())
+ (((x)=((e+1(00) (((0)-
v==+1
To simplify the notation, let
((41(1(()) Tr(P Cov [W, (()))) + 2E
Σ r=#+1
$ T
T,111 Pr+i w W1/11)
Wi Ie(0)
E V (+1 (4++1())) [0)).
We see that the expected Q function given by
E Q (x, u; E) (0)
= x T Qux + T Ruu + E C (Aer Buu+ + W; [.00]
20

---

= x Qx
=x0 + u Reu + (Axr + Buu) T Pi+1(A + Bru)
TRu
T
T-1
+2 Piti
Σ
: P++1 Pr+,
(Aax+ + BBU) + (7:(1(
+=#+1
T-1
= .RT(R, + B, + PitIA + PA-i
Φ Σ r=t+1
P. Prta
Biu
1/1
+ x (Qt + A, Pa+ Ar)a (
Σ T=t+1
$
Pr
P++i W
AeT + (44((1(0))
r,1+1
= -(u+ KtT - up (L((0)) (Re + Bi P+) (u + Ket - ul((4( + +5= (x;
where V¹² (z; (f)) is given by
T-1
AT P++1A)) 2 (Qt A7
PrtIWaf t/e +
Σ 7=t+1
T 7 Pr+ Pr+i Wole
ApT + (1+1
+ (Kxz a. (R++ BB (K,z - प. (I((0)))
Using the expected Q function, we know that the optimal policy will pick the action
Te (x; (())) = arg min E [or (x, E) I,(0) Ka + ul (0).
Therefore, we see the optimal cost-to-go function at time step t is given by
cF (1; T((0)]
= + (Krz uZ ((((K))))T(((K
RA(Ket - -
+ ((A, B,K,)æ (ET B, B,K,)o + (T,(O)
P2+i((A,
+2 Po4i + Σ
T T Pr+ Prii Woy 7/e
((A,- BeKi) ((K)) B,o, (+((1)
r=++1
= = + K2 RyK, + (A, B,K,) P Pt+ - BeKi)) 2 R2K,v
+ 220 (I())) B, PitiAA B.Ka)æ
T-1
+2 PutiWil+ +
Σ T=1+1
7,111 (1+1P++a
(A, BB,KK))
+ a (4((0)) (() + B, P4+1 Bi B,) (L((()
T-1
+ 2
Peti tje
+
Σ
T
T.41 P++ W
B. (4(00) + (1.()).
m=t+1
Note that the term 227 (0) R2Keæ and the term +20 (4, (0)) B, PAt B,K,) cancel out because R. = B, Pt+ (A. - B,K,). We also note that the matrix in the first quadratic term can be simplified
Qc + KJ R₂K, + (Ai - B,K,) T
-Q++ KT B, P++ ( - B,KK)) + (Ar - B.Ki) Pit1 ( - B,Ki)
=Q.+ A, Pi+ (A. -BrKa)
-Q.+ A, - P
=Q++ + A, P.+1Ac -A, Pe PeHHH,PetAA
Pt:
21

---

where the last equation follows by the definition of P. in (5). Therefore, obtain that
E CT (x: 1((0)
T-1
=x =x Pro+2 2 (A, - -AT
W +
Σ r-t+1
T
17.11 P w. W (t)) x
+ (T,(0)) (Rr B, Pat1 B.) B.)a (T((O)
+2 PitiWal
$ 7,,41 Pr+1 Σ
Wii
(, + (
T=H+1
T-1
x PPx +2 2
Σ
W
x (.1(0).
where the residual term (()) is given by
(.())) = (O) (Re + B₁ Peti B.))
+2 Pi+1W A/e
+
Σ の T T=H+
(.(()) - (1:()).
Thus, we have shown the statement of Proposition 3.1 and 16 by induction.
A.2 Proof of Theorem 3.2
Note that the cost-to-go function CT (ar; {) can be expressed as Q7 (x; Substituting
the expression of 7 (0)) into the expression of E [Q (r, (0) = ([0]]
Proposi-
tion 3.1 gives that
E Q (z, u C (z: 3) 3) ((0) (0)
(u n| (z; (0)))
(R, + B, Bi) T (2))
(17)
Substituting u = (0) into the above equation gives that
[QF (1,, CT (z; E) 1((0) = (0)
- = =f(
+ B, P (z) ())=)(()))
(ol(u(0))=u)(( (O)() (R, B, (t)) Tr((Re + P (T) (v)( (
(18a)
ap (0))
(18b)
where we use the expression of optimal policies in Proposition 3.1 in (18a) and rearrange the terms in (18b). Note that by Proposition 3.1, we have
2 (0) E (I)) (())) = (()))]
Therefore, by the tower rule and the definition of conditional covariance, we obtain that
E QQ (a, (1,a)( CT (x; (0 = (0)
= Tr( (T [u] (L) I((0) = (0])
(19)
Let {(X,, denote the (random) trajectory achieved To-T under problem instance E. Since X, meaasaaale by (19), we obtain that
E |or" (X,, - C7 (X:=) [=(0)]] Tr + BT P1t1B, [n] (L())) [=)
(20)
22

---

where we use -,= (((;)(()) Note that we have
Oi (X U,; E) - (x,,, C (
Substituting this into (20) and taking expectation give that
E hie
U2) + C7+1 (X++1: o7 (Xt:3) (X,, Xx,
(R, + B, Pr+1 B.) Coov [1] (T,(O) [+(O]]]]-
(21)
Summing (21) over f = 0, , - 1, 1, we obtain that
T-1
E
he (x, U,) Ci (Xu; 3)
=
Σ
Tr((R, B. Cov (1(()) (F(0)))F((())))) [+]
1==
1=0
Note that the left-hand side equals P(0). Thus, we have finished the proof of Theorem 3.2.
A.3 Proof of the MPC form
In this section, show that the MPC policies defined in (7) and (8) are equivalent to the optimal policy Proposition 3.1.
To simplify the notation, we define the large vectors
Tt Ft++1
Ut
Wi
W1++1
T :=
and WT
FT
LUT
[UT-1
Follow the approach of system level thesis, know the constraints that #++1 == A,I, + B, + Wy, for r 2 t, and D4 = x
can be expressed equivalently by the affine relationship
= 2 x + 2. + 1 W7
Let Q Qr- Pr) and R Diag Re..... RI-1). We know the objective function
(with equality constraints)
T
Σ
Nor (K W+) + hr((T)
s.t. Ee4+ = (x w;), for 7 2 t, and He = x,
(22)
can be written equivalently in the unconstrained form
$ U2xx + uu + ww) Q(2 + 2. + $ t) + it Ret.
(23)
We introduce the notations
W Wa W
w
We W41
WH
We =
and 2. =
1|t
WT-1
W T-1 1p
w
1pe
The MPC policy in (7) can be expressed as
min ( x0 + i. i7 + W) Q(0
+ Ww + 17 Riz I(( = (1(0)]
=((}))
Because the objective function can be reduced to
E ( x + P. 2 W) Q(0 x + t. Ww + TI PoT [,(0) = (0)
23

---

= x x + Pui + T ww ( Q _2 + Pu a + t u :t
Rui
+ E (o (W w)) Q$ (W w 1,(0) 4 [0]
where the last term is independent with I and 17. Thus, the MPC policy in (7) is equivalent to
E ( + क. v7 Pm W) T Q(P P. W) a Rdt I ( (x())
which is the MPC policy in (8).
Now, we show that (8) is equivalent to the optimal policy in Proposition 3.1. For any sequence W,T-1, let MPC wcT-1) denote the first entry of the solution
T-1
arg min WeT
Σ (xT, un) + hx((T)
r=t
s.t. 2++1 = (I( Uy; we), for r 2 1, and Ty = I,
(24)
To show that (8) is equivalent to the optimal policy in Proposition 3.1, we only need to show that
T-1
MPC WcT K, - (Re + B, Ps41
Σ Pr
(25)
holds for any sequence WcT-1- To see this, we consider the case when W1:T11 are deterministic disturbances on and after time step i.e., the agent knows Wr7-1 exactly at time step In this scenario, we know the optimal policy is to follow the planned trajectory according to MPC in (22). On the other hand, by Proposition 3.1, we know the optimal action to take at time is -K - (Rg + B, Bc) (,) ---1 1 11 Therefore, the first step planned by MPC must be identical with - K2æ- (Re + B P B,)-1,, B, Σt= TT 7+1++1 P Thus, (25) holds, And replacing wx(r-1) with w (T]- finishes the proof.
A.4 Prediction Power Evaluation
Based on our discussion in Section 3, we propose an algorithm (cf. Algorithm 1) evaluate the prediction power efficiently given a set of historical problem instances {5.1 Recall that we define the optimall action
m = - (Re + B, Pe+ Pet1 B,
Σ E T-t
(26)
which is the optimal action that agent should take with the oracle knowledge of all future disturbances at time I. In the prediction power given by Theorem 3.2, we can express uद (T, as [ (E) [e)0] by Proposition 3.1, which is the expectation of it (E) condition on the history at time step t.
We design Algorithm as follows. While iterating backward from time step T - 1 to 0, the algorithm first constructs dataset of the surrogate optimal action (E) as the fitting target. Then, the algorithm estimates the covariance of (E) when conditioning on (0) and (0), respectively, using a subroutine (Algorithm 2). The last step of Algorithm gives the predic-
tion power because E Cov [a] (T)( [:]]]]] can be decomposed as Cov (u; (E) [.]]]
E [Cov ( (=) [.)]],, and prove this result in Lemma A.I. This decomposition is helpful because otherwise, we would need to evaluate the conditional expectation inside another conditional expectation. Specifically, n. (0)) needs to be approximated by learned regressor (say, Φ) that takes (0) an input. Then, to evaluate E [Cov (I)) (O)]]. we would need to train another regressor to predict the output á. Our decomposition avoids this hierarchical dependence.
Lemma A.I. For any random variable X and two o-algebras F C F, the following equation holds
E [Cov [E X F'] F]] = EE [Cov XX F]] [Cov [X F']]
Proof of Lemma A.I. By the law of total covariance, we see that Cov [XF] Cov E
Cov /o
24

---

Algorithm Prediction Power Evaluation
Require: Dataset D of problem instances {En) I==
1: for T 1,7 2. 2.....0 do
2: Compute Pt: Hc: K and be2 according (5) and (6).
3: Compute M,-- Rs + Bi Br.
4: for n = 1, .,, .V do
5: Compute ut (Sn) according (9) in problem instance f..
6: end for
7: Call Algorithm 2 to estimate y Cov
a (E)
4[(0]]] using (
8: Call Algorithm 2 to estimate D = Cov
7 Tx(0]] using (())
9: end for
return P(O) E Tr (.. Eio Tr [r
Taking expectation on both sides gives that
E [Cov [X
[F]
F. CCov [X
F1) [F] + [Cov [X [F'],,
which is equivalent to the statement Lemma A.I.
Evaluation of the Expected Conditional Covariance. For two general random variables X and Y. we follow a standard procedure to evaluate the expectation of their conditional covariance E [Cov [Y X]] using dataset {TT,, }nr} that is independently sampled from the joint distribution of (X, Y) (Algorithm
2). The algorithm first trains a regressor yb that approximates the conditional expectation E [Y] X]. where we the definition:
[[Ix -
E E X]
min
E
any
Then, et is used for evaluating the conditional covariance. During training, we split the dataset into train, validation, and test in order to prevent overfitting.
Algorithm 2 Expected Conditional Covariance Estimator (ECCE)
Require: Dataset D that consists of input/output pairs (Øn, Vn).
Split the dataset D to Duniny Deat, and Diest-
2: Initialize regressor v with input a: and target output y.
3: Fit db Dunin with MSE and use Dval to prevent overfitting. EnDD (ynn (z) (
4: return ==
A.5
Details of Examples in Section 3.1
In this section, we present the specific instantiation of Example 3.3 in Section 3.1 and another example (Example A.2) for the mismatch between prediction power and prediction accuracy.
A.5.1
Instantiation of Example 3.3
We instantiate Example 3.3 with the following parameters:
0.1 (0.). Q -
0.1 0 1 B-
R -=)==)),, (0)=((()_==
.))
0.99
A
and
0.141
Under different values of coefficient V.(0) (or VT))) over a train dataset with 64000 independent samples. We plot in the MSE curve on test dataset with 16000 independent samples in Figure 4. From the plot, we that the predictors (0) and (T(T) achieve the same MSE when predicting each entry of W, under each PE E {0, 0.1,,.,,,,0.. 0.73.
train linear regressor to predict each entry of W, from
Then, we use the trained linear regressors as w and WT to implement the optimal policy in Proposition 3.1. We plot the averaged total cost over 16000 trajectories with horizon T 100 in
25

---

3.92
MSI C. 100
1663
3002
0.
2352
Thametoo cali
2393
0.0
61
0.2
6:3
84
6.5
0.6
6.7
0.6
0.2
0.4
0.5
0.5
60
Coeticeer 5
Confidern p
Figure 4: Example 3.3: MSE p curve.
Figure 5: Example 3.3: Control cost p curve.
Prdiake (utep
0.30
0.25
102
0.15
20
100
Figure 6: Example A.2: MSE - time curve.
Figure From the plot, we see that the optimal policies under the predictors V2( and VT(T) achieve significantly different control costs when p > O. We also plot the theoretical expected control cost in Figure to verify this cost difference. Running this experiment takes about 50 seconds on Apple Mac mini with Apple MI CPU.
A.5.2 An One-dimension Example
We also provide example with 1, where the prediction V. is correlated with two steps of future disturbances W. and W1+1.
Example A.2. Suppose the disturbance at each time step can be decomposed as W. = E W(O) where the {W(")) 22 are independently sampled from three mean-zero distributions. We compare two predictors: V1(1) = (w(", w and V+(2) = (w!") + +W(") + -AAT ATT PW:)) 6+1 They have the same prediction power when used in the control problem because
a(((4(2)) = P (w:") +w!")) + (AT - PHHPPW (1) 41 (.(())
However, know that F((1) is strict super set of F((2), thus Vi(1) achieve better MSE than V2(2) when predicting the disturbances. This is empirically verified a ID LQR problem with = Q = R= = (1) and wi()) lid N(O, 1), as we plot in Figures 6. the simulation, we train linear regressors to predict W, and W with the history (1) or I,(2) for each time step t T 100 over a train dataset of size 160000. Then, we plot the MSE time curve on a test dataset of size 40000. Running this experiment takes about 270 seconds on Apple Mac mini with Apple MI CPU.
26

---

A.6 Details of Example 3,4
We instantiate Example 3.4 with the same dynamies and costs as Example 3.3, i.e.
1 0.1 1 B
(..1 0.1
(' (). and R (1).
A
Q
To build the predictors, we sample the true disturbance W. iid. NO,, and fix the coefficient p 0.5.
The online policy optimization starts with the initial policy parameter To = 0. When implementing M-GAPS in both scenarios, use the decaying learning rate sequence 1}: (1 + 1/1000) (0.00) -0.5 The optimal predictive policy for using Vo.--1(1) (1) or Vo.c-(() are T0rr-1 and To:T-1 whose closed-form expressions are given by Proposition 3.1. Note that for the history (1), the optimal predictive policy ne only depends on (1) because all other entries independent with future disturbances Wt. -1- Similarly, for the history 4e (2), the optimal predictive policy गद only depends on ut- and vz(
2
In Figures I and 2, we compute the average cost improvement of M-GAPS (or the optimal predictive policy) against the optimal no-prediction controller (.))) = Kx. That is, on each problem instance plot
t 1 (-(cost of M-GAPS until time t) + (cost of until time t))
for time t 0, 1....,,T ......,TT1. - The prediction power (averaged over time) is given by P(0)/T. We simulate 30 random trajectories with T 80000 and plot the mean with the 25-th and 75- th percentiles as shaded areas. From the plots, we see that M-GAPS' average cost improvement converges towards the prediction power prediction power in the second scenario. This is as expected, because the optimal predictive policy oं not in the candidate policy set of M-GAPS in the second scenario. Simulating the first scenario takes about 200 seconds on Apple Mac mini with Apple MI CPU. The second takes about 210 seconds on the same hardware.
time in the first scenario but stays far away with the
B Proof of Theorem 4.3
Since we assume Zo is the initial state (deterministic) and π. is the optimal policy under the predictor with parameter f, we have
CT (ro: (xo: = =0)
E
Similarly, we also have that
E [ (rrp: =)] =
Let {Xu.r. 1 be the trajectory of the baseline controller Terr- under instance starting from Xo = To. First, we will prove by backwards induction that the difference in cumulative costs between the optimal controller x² and has the following decomposition:
(zo: Că (ro: E) = Σ (cr (X₂ Qi (x.,0:
(27)
For the base case time T we apply the definition of CF= to get
(XT -7 - CT Q7 (X
For the inductive step. suppose that
T-1 Σ
- (C
(X,; QF' (Ke, Ur:)))
t=
Note that for any 1 < T,
U;; Qi" (8, 0, (XH1(())))))) (x+1(x++1))
27

---

Therefore.
- -Q,,) 3,:3)
(X,:3)- (X,
(X+, Ur:
- - B)]
(X;; 0² (X,, 3r + Σ
of (x+,
1=1+1
T-1
Σ Ci (Xx;3) - of (X,, (K,U0;;))
This completes the induction.
Next, define U2 == x. (X,; (e))). Note that Ug is - and U, F, measuuablle and therefore also FF (0)0)mmaauurabl Because assume the matrices Mo.T satisfy Condition 4.1,
E
C (X,; E) (0) - E oF ((00) [00 M, - U.) -
-.) J. (28)
Let U, = E (U, [O)] We see that
E [U, U.)(U, U.)T 4(0)
E [Ō: -U,)(U, U.) [(00
E [U, U.)(U, U.)_ [(00]
+E [[(( [[(0e Ú.)(ū, U,) [400] + E [ Ü,)(U,- - [(()
Cov (x;; ((())) [(0) +E Ü. - U. [[(0]] (U, Ú.)
+ +U, - -U)-U Ü. U, T.(0) +(G - 00) T.)
(29a)
Cov (X:; 4 (0)) [.(0)] + (Ü, - -U, - U.)
(29b)
where we use (Ü, Ú,) is F meeaasurrllle in (29a); we use the definition of U, in (29b).
Applying the towering rule in (27) and substituting in (28) gives that
E C (zo: CJ (mo: }
E
(Xx:)) QF" (X,,U,;
T
E
(Xx:E)
T((0)] - [Q (X,, U.))) [(]]]]
T-1
<
Σ
E -
Tr TMMM [C, U,)
(30)
If the stronger Condition 4.2 (a) holds, by (29), since X, is - we have
E [ - U.) J = E E [CU, U,) - U.)T | [O]]]
> E Cov (x(: (4) ž E,
(31)
Then, we can apply (31) in (30) to obtain that
T-1
C (ro; =) (2oi 3) S Σ Tr.ME..
(32)
28

---

Else, if the weaker Condition 4.2 holds, by (29), since X, is Fi measurable, we have U.)
(r(E [ [ -
U = Tr [CU U.)(U, U,) [[OO]]]
2 E [T< (Cov [T[ (Xx; (())) I.(0)]]] 2 dr.
(33)
Note that for any positive semi-definite matrices A, B, such that A - C = have
Tr(AB) Ir(CB) Tr((A - C)B) 2 Tr(CB). Since M, č Mmin 4, we can apply (33) in (30) to obtain that
E C (zo: E) Cā (au: E) S
Tr Mmin (M)) E [ UN( T
Pmin (Me)
C Proofs for LTV Dynamics with General Costs
In this section, we first provide proof outline of Theorem 4.8 (Appendix C.I). Then, we discuss an example where the MPC in (7) is suboptimal (Appendix C.2). Lastly, we provide the proofs for the key technical results required by the proof of Theorem 4.8.
C.1 Proof Outline of Theorem 4.8
Assumption 4.5 makes two requirements about the well-conditioned cost functions, which are standard the literature of online optimization and control [3, 4]. For the last requirement, we additionally require L < 1, which implies that the system is open-loop stable. Under Assumption 4.5, the expected cost-to-go function a well-conditioned function, which is important for establishing Conditions 4.1 and 4.2 (b). We state this result formally in Lemma 4.6 in Section 4.1, which establishes uniform bounds for the strongly convexity/smoothnes of the conditional expectation of cost-to-go functions: 14, is uniformly bounded below by Mh and is uniformly bounded above by I-LA
We present proof sketch of Lemma 4.6 and defer the formal proof Appendix C.4.
Starting from time step T, we know the cost-to-go OT (z; 3) equals to the terminal cost h (z). satisfies the strong convexity/smoottness directly by Assumption 4.5. We repeat the following induction iterations: Given E C7+ (æ; E) [+))(0) time + 1.we define auxiliary function that adds in the disturbance residual W. W and condition the history time &:
(Z; = E C (x W, W =) I.(0) sz(0)
(34)
can be expressed as E CT' (x + We Wi [0)1 (((0) = :1(0) by the tower rule.
Thus, we know function C is strongly convex and smooth in because these properties preserved after taking the expectation. Then, we can obtain the expected cost-to-go function hi (x)) + min, (N((w) + C + B,u + (e))) We existing tool called infimal convolution study the optimal value of the this optimization problem as a function of æ. Specifically, define an operator Og:
CT (1; (0))) = (0)
(fD)w) (x)
min (f(u) w(x Bu)} for f m R and w R R. "ERr
(35)
One can show that if and w are well-conditioned functions, then (/Onw) is also well-conditioned (see Appendix C.6 for the formal statement and proof). We can use this result to show the expected
cost-to-go function E CT" (x;; 3) I,(0) (0) 1 (xx (., (Ar w (0)),
is also well-conditioned in æ at time step f, which completes the induction.
If w takes additional parameter w, we denote (f[Dw) (æ; w) m (f(u) + w(x Bu:w))
29

---

For the second condition on the covariance of TT's actions. we note that A0(0) in Assumption 4.7 should be positive as long as (e) has some weak correlation with W. Under Assumption 4.7, we can express the optimal policy
TH (x; (()) = arg mrg (wr(w) CF + Beu + W:))).
(36)
(+1 in (34) requires the history (0) as an input, it no longer While the original definition of Cz+1 depends on the history under Assumption 4.7. We defer the proof to Appendix C.5.
We can express म. (x;; (0)) as the solution to C2 (A(+))A(Wut)) Wej)). For some distributions including Gaussian, the covariance in the input of an infimal convolution will be passed through to its optimal solution. Specifically, let u(yD)w)(e (2) denote the solution to the optimization problem (35). When and f are well-conditioned, we can derive lower bound on the trace of the covariance Tr(Cov Cov [w) (X)] } that depends on the covariance of X. Due to space limit, we defer the formal statement of this result and its proof to Lemma C.2 in Appendix C.6. Using this property and the observation that n. (æ; (f)) can be expressed as " (hh B or (A,r + W t/e we can directly
verify that Condition 4.2 (b) holds with
nd.(0) NB Tr Cov (x; F((O)]] 2 or 2(e, + (++1VBB)
(37)
Since Lemma 4.6 and (37) imply that Conditions 4.1 and (b) hold with M. uel and respectively, we can apply Theorem 4.3 to obtain the prediction power lower bound Theorem 4.8.
C.2 Example: MPC can be suboptimal
We first highlight the challenge by showing that MPC can be suboptimal, i.c., only planning and optimizing based on the current information might be suboptimal when the cost functions not quadratic.
Consider 2-step optimal control problem (1-dimension):
X1 = Xo + Uo. and X₂ = X1 + U1 +U+
The cost functions are given by
12z if S 0, +00, otherwise.
ho(x, u) x² + uu² (1(2, x² uu² and h2(x)
Suppose W, is random variable that satisfies P(W, 1) p and P(W, 0) 1 p, where 0 p < 1. At time 0, we don't have any knowledge about W, (i.e., W, is independent with (0)). However, time
can predict W, exactly, which means o (WW) C (0).
Suppose the system starts at To = 0. At time step 0, MPC (7) solves the optimization
min E (Xo, uo) + h (X,, 41 + h2 (X2) (0)
s.t. X, 0, X; X, + No: X₂ X, + u1 + W1.
(38)
Since Io( is independent with Wi, the optimization problem can be expressed equivalently as min of + (uî + uf) + I. (12 + + + Wi)]
min 2ng + u 1, s.t. ug + u1
The equation holds because the planned trajectory must avoid the huge cost at time step 2. Solving this gives uhg Thus, implementing MPC incurs total cost that is at least 2ng 2 In contrast, one just pick 24p = 0, the agent can pick ú1 based on the prediction revealed at time step 2:
00 81 [
if W1 = O, otherwise.
In this case, the expected cost incurred p. Thus, we can claim that MPC is not the optimal policy when p < 2. The underlying reason that MPC is suboptimal is because it does not consider what
30

---

information may be available when we make the decision in the future. In this specific example, since Wi is revealed at time 1, we don't 't need to verify about the small probability event that leads to huge loss.
We dive deeper into the reason why MPC (7) is optimal in the LQR setting (Section 3). Note that the expected optimal cost-to-go function at time step 1 is
E
R (x: 3)
[()))
min E [11 (2, u1) + h2(X2) 4 (6)], s.t. X2 = d1 + W1. (39)
Here, in is F0) And the true optimal policy at time 0 is decided by solving
min ho un) + E O [ (X1;E) To(0)] s.t. X1 = x + ug-
ug
In general, we cannot use
1i (h1 (X1, u1) + h2( lo(0)) s.t. X2 X1 u1 W1,
(40)
to replace E CT (X1; [0] like what MPC does in (38) because here in is FoeOu-umasur
in (40). Recall that #1 is (2())))aaurabbll in (39) and Fo (0) is subset of Fi) However, in the
LQR setting, as the closed-form expression (16), the part of E CCT (X1: Ib(0) that depends X1 will not change even if Fi (0) changes. Thus, we can assume (0) Fo) without affecting
the optimal action at time 0. Therefore, MPC's replacement of E (TT" (X1: Lo(0)] with (40) is
valid in the LQR setting.
C.3 Infimal Convolution Properties
The first result states that the variant of infimal convolution preserves the strong convexitylsmoothness of the input functions. The proof can be found in Appendix C.6.
Lemma C.1. Consider variant of infimal convolution defined as
(SDnw) (x) min (u) + w(x - Bu)},
(41)
where f 1R + IR, w R" + P. and B E Ruxm is a matrix. Suppose that f is a p strongly convex function, and w is a (tu-stonggly convex and fu.-shooth function. Then, f is a My+|
Hully
strongly corvex and smoohh function. We also have ((fL)w)(()) = Vw(x - Bu(x)).
The second result is about the optimal solution of the variant of infimal convolution. states that for some distributions, the covariance on the input will induce a variance on the optimal solution. We state it in Lemma C.2 and defer the proof to Appendix C.7.
Lemma C.2. Let ((DDm) (x) denote the solution the optimization problem (35). Suppose function is p stroongyy convex. Function w is str-ongy convex and Ey--shooth. Suppose X is a random vector with bounded mean and Cov =x==E agI. Further, there exists constant > such that for any positive integer N, X can be decomposed as X = =EN for i...d. random vectors X, that satisfies TE [|XxI]]] CC. Then,
Cov (X))) 2 no Gmin (B)2 2(1, + f. BB|)2
As remark, an example of X that satisfies the assumptions is the normal distribution X ~ 20,
We have X₁ ~ (0, E/N), thus E [ < 3rr
The next result (Lemma C.3) considers the case when there is an additional input to function w in the infimal convolution. When this additional parameter causes a covariance on the gradient V [Iw W), the optimal solution of the infimal convolution will also have nonzero variance.
31

---

Lemma C.3. Suppose that w(z, w) satisfies that w( w) is an Em-shhoth convex function for all w. For a random variable W, suppose that the following inequality holds for arbitrary fixed vector E R
Cov VV W)) = oul.
Suppose that f: Imm - is (l--Stonnyly convex and l y-smooth function (m S n)) Let B be matrix in Raxm, Then, the optimal solution of the infimal convolution
"(SCBw) (I, w) = arg min (f(u) w(x Bu, w))
satisfies that
n10 mmnn (B2
Tr( Cov [wr (2,
2(6 + Ew [1]}²
holds for arbitrary fixed vector z, where min (B) denotes the minimum singular value of B.
Lemma C.3 is useful for showing Lemma C.2. We defer its proof to Appendix C.8.
C.4 Proof of Lemma 4.6
We use induction to show that E CT (x; 4(() = c0)) is pe-strongly convex and 4-smooth function for any (f), where the coefficients fe and l, are defined recursively in (14). To simplify the notation, we will omit (0) =" the conditional expectations throughout this proof when conditioning on realization of the history (0).
Note that the statement holds for T, because E CF (x; ur(()] = (x(()) and the terminal cost he is -t--ttongly convex and ---smhoth.
Suppose the statement holds for t 1. We see that
C (x: E) (0) = h (x) + min (h Cz (Air Buu + Wx | ((())).
By the induction assumption, we know that EE O 444 (441(0) (0) is sttroglrnglyy convex and tmoo-smooth function for any (0). Thus, E Csa (++ Wú; B) (x())) also -stoonnyyy convex and -mooth function. Therefore,
min (u) E (CT B,u W; 44 (e))))
Mullee -stoongly convex and 4441-mo function of x by Lemma C.I. By changing the is a +iu+b"me variable from x to AgT, we see that
min [b (u) + CT + Buu + W; ((())
a MA
Mu -trongly convex and LA 1++1 function by Assumption 4.5. Since hy is Ne +
Ma stronnyy convex and smoth function, see that IE [CT" (x; (0) is also pe-strongly convex and f--smooth function because
MuHe+1 and ly Eg + la le+1.
Hi Uz + MA
Ha. + 62
C.5 Proof of Theorem 4.8
Note that the optimal action at time step is determined by
T (x: [())) arg min h1 (w) + E CCt (Aix + Bau + WxE) | (I(0))
(42)
32

---

This can be further simplified to
T. (z; [(()) = arg min (hr(x) + C Of + B + W((e).
The additional imput (0) is not required for C741 because the function C (z; (0)) does not change with the history (0) under Assumption 4.7. The reason is that W, w and all future predictions and disturbances W1+1T-1, V 14:77-1 are independent with the history (0)). By (36), that
t/e
my (z; [+())) " "(hy0- Cz4 ( Wije)-
Under Assumption 4.7, we see that
Cov W = Cov [Wa] - Cov [W, Vi(0)] = (O)
and W is Gaussian. Therefore, we can apply Lemma C.2 to obtain that
nde(0)pf+1 FB
Tr Cov (x; F(OO]] 2 of = 2(ly + 4+1 (+)
Thus, Condition 4.2 (b) holds with oe.
On the other hand, Condition 4.1 holds with M, = I4l by Lemma 4.6. Therefore, by Theorem 4.3, obtain that P(O) 2 E p.
C.6 Proof of Lemma C.1
By the definition of conjugate, we see that
BfD (v) max (v.a) min (f(u) w(x Bu)]
(43a)
max (1y,a) f(u) w(r Bu))
max (yy, Bu) + (v, Bu) - f(u) w(x Bu)}
max max {(y,, x - Bu) w(r - Bu)) + +(B y, u) f(u))}
(43b)
max max {y,, Bu) w(z Bu)) + (BT y, u) - f(w)
max (w" (y) (B" y, w. f(u)}
(43c)
= w (v) + ( v).
(43d)
where we use the definition of fß (43a); we change the order of taking the maximum and use (y. Bu) = (B" u) in (43b); we use the definition of w in (43c); we use the definition of f in (43d).
Since fD is convex, by Theorem 4.8 in [26], we know that
Bf (v) (w) +B
(44)
Since is a -tr-onyy convex and fu-smhoth function, we know wn is an -stronngly convex and -smooth function by the conjugate correspondence theorem [26]. Similarly, we know that f* is a By smooth convex function. Thus, we know that w" (y) + f (B' y) an /.- stronnlyy convex and
[|B||3)
smooth function. Therefore, by the conjugate correspondence theorem, we know that
P
M+
Bl is
P-P
-strongly convex and em-smooth function.
[ Pm.
Now, we show that
(x) = Vw(x - Bu(x)).
(45)
33

---

Following a similar approach with the proof of Theorem 5.30 in [26], we define 2 Vw(x Bu(x)).
Define function (( == (f=nw)(z {) (f-nw)(z) (E, 2). We see that
( (x) + (fD (5
I w(x + & -B(())) - w(x Bu(x)) - (5,2)
(46a)
I (E. Vw(x + Bu(x))) (5,2)
(46b)
(S, vwlx + -Bu(x)) Vw(x - BB(()))
I IlEll NVwxx+ Bu(x)) - Vw(x Bu(=))]
(46c)
(46d)
where in (46a), use
() + S f((x))) + w(x + Bu(x)), and (fInw) fu(()) w(z Bu(x));
the convexity of wt in (46b); we the Cauchy-Schwarz inequality in (46c); we use the assumption that w -smoohh in (46d).
Since (fD is convex function, & is also convex, thus we see that
(<t 2 20( ( - 2 11
Combining this with (46), we conclude that lim (0(()) 0. Thus, (45) holds.
C.7 Proof of Lemma C.2
By Theorem D.I, we see that
Cov [Vw(X)] 2 aopl
Then, we apply Lemma C.3 with the second function imput to the infimal convolution as W(z, w) = w(x + w). In the context of Lemma C.3, we set W X, so the assumption about the covariance of the gradient holds with
Cov (, W)] 2 J.pla
Note that for any fixed w, W(, w) -trongly convex. Therefore, we obtain that
nopp Tmin (B)²
Tr [Cv [[]]D]))()]]] Tr(Cov [uro (0, 2
2(e, + L B1)
C.8 Proof of Lemma C.3
Because function is sm-sthhh, we have
Vo(u(z, w)) Volu(z, WIl) < fcllu(x, - u(x w
(47)
Because function is l -smoothh have
B Vif (x- - Bu(x, w), w) B Vif - Bu(x, w'), w'lll
> Vf (x= B Ew [u(2, W) w) - B vif(x B Ew [u(x, w')l
w'll
||B BVVV VIS(x
B u(x, w), w) B TV, f xx B EEw [u(2,, W)] w)ll
- VVV - B u(z, ) w/) B V Vif(x Ew [u(E, W)] w w')ll
(48a)
> B Vif(z= - B Eww [u(z, W)] w) - B Vıf(I - Ew [u(I, W)] w')ll
- 11 ([ w) - Ew [u(x, W)]l + ||u(2, w') - Ew [u(z, W Will))
(48b)
where we use the triangle inequality in (48a); we use the smoothness of f in (48b).
Note that by the first-order optimality condition, we have
Velu(x, w)) B Vif(x B ul(r, w), w) = 0.
34

---

Therefore, for any w, w', we have that
Vc(u(z, Ve(u(z, B Vif(r- u(x, w) B Vif(1 - B- u( w w'). (49)
By combining (49) with (47) and (48), we obtain that (ellu(2,, w) u(xz w'll + 2 || (1lu( w) Ew [u(z, wi]ll + [|(( w/) - Ew [u(xr, W)ll) VB f B Ew [1(a,, w)]. w) B vif(2 B Eww [u(x,, W)] |||
holds for arbitrary w and w'. Let W" be random vector independent of W and have the same distribution. By replacing w/w' with w/W' respectively, we see
(x)lu(x, (1, W) - u(æ, W
+ e ||B|I (1lu(xe W) - Ew [u(ar, W)]l + ||v( W") Ew [u(a, WillI)
2 | ViS(x - B Ew [u(2r, W)], W) - B vi5(x - B Ew [u(x, W)], W*)||
which implies
(C. + B/BBI) (1) W) Ew [u W)ll + || W Ew [u(x, W)llI Ew [u( W)], W) B V Ew [u(z, W)] W
Σ B Vif(x
(50)
by the triangle inequality. Taking the square of both sides of (50) and applying the AM-GM inequality gives that
2(ee + [[1(11)(((((E,,)))))))))))))))), W) Ew [u(x, W)]l + 2(c + B1)) [u(r, W") Ew [u(2, W)]l
> B VI/( B- Ew [u(a, W)], W) B V. - B Ew [u(2, W)], W)],
(51)
Let v1f B- B- [u(x, W)], W) V.f(x B. Ew [u( W)] W Note that the right- B y|1 = Tr( B (YY BB} By taking the expectations of
hand side of (51) can be expressed as both sides, obtain that
A(e. + BI) Tr/Cov (u(z, w))} 2 2Tr (BT Cov VV BEW [u(z, W)] W B}
> 2 min (B)
In the last inequality, we use the property that the trace of a positive semi-definite matrix equals the sum of its cigenvalues. Thus, it is greater than or equal to n times the smallest eigenvalue mnami (B)² Rearranging the terms finishes the proof.
D Useful Technical Results
In this section, we state useful result about what functions can pass the covariance of its input to the output in Theorem D.I, which is used to show Lemma C.2. We defer the proof to Appendix D.I.
Theorem D.1. Suppose that function gd + Rd satisfies
(g(x) - g(x'((())))))))))) x²) 2 7||z z11?, and [Ig(z) - g(x')) ll L||= - I'11, Vx, Rd.
(52)
Additionally, there exists positive constant such that
-I1 3 (x) = f1, Vz E E R i [d].
(53)
Suppose X is random vector that satisfies E [X]] < co and Cov [X]= μI. Further, there exists constant C' 0 such that for any positive integer N, X can be decomposed as X Σm X; for i.i.d. random vectors X; that satisfy IE
||xx 11 < C - Then, have
Cov [g(X)] = 1
As remark, the gradient of a well-conditioned function satisfies the conditions in (52).
35

---

D.1 Proof of Theorem D.1
Without any loss of generality, we assume E [X] because we can view g [X] + as the function and subtract the mean from the random variables. The assumptions about g and X in Theorem D.1 still hold.
For any E [d] and e E IRdd we have the Taylor series expansion Lagrangian form (see Chapter 3.2 of [27])
(
V gi (x())))))))))))))))(()) e
(54)
2
where g(() is point on the line segment between a and æ + e. For notational convenience, let
V g1 (z(1)e
Vg(x)= =
E Raxd and (x,,)
e ER.
V 9o((
With the above notation, Eq. (54) can be equivalently written as
g(x + - g(x) = Vg(z) c+ 2 (z)
(55)
From Eq. (53), know that ( E||e|| which implies In addition, by Eq. (52), we see that
||0 e) S evdlle|?
(56)
(g(x +) - g(z). <) 2 7|<l/
Substituting Eq. (55) into the above equation and rearranging the terms, obtain
Vg(z) . >llell - e (2,,),
which is equivalent to
V + Vg(x) E >/le|12 T - (z,
2
Observe that the term subtracted from the right-hand side satisfies Te vi (x,,)) S @vd]eell" which follows from Cauchy- Schwarz inequality and Eq. (56). Therefore, since the previous inequality holds for any E Rd, taking + 0 gives that
Vg(x) + V ITI.
(57)
2
Before we proceed, we first state and prove a lemma that can convert the summation in Eq. (57) into a product form.
Lemma D.2. Let M E Raxd be a real- valued matrix satisfying M + M 2 2yI. Then, for any positive definite matrix Σ I/2 pI, we have TEM ž I
Proof of Lemma D.2. Since M M 2 2 T, we have for any x Rdd that
27|1=1|
2x T M r 2x T - 1/2g1 T x < 2/2 xl1
< 24 1/2 | 1/ M x||
where the last inequality follows from Σ b pI Rearranging terms, we obtain
|/11/2|||
V T S -/1
yu 1/|x//1 I || x]|.
Squaring both sides concludes the proof.
Next, we state and prove a lemma about the lower bound of the covariance induced by an additive random noise on the input that is useful when the noise is sufficiently small.
36

---

Lemma D.3. Let E be a mean-zero random vector in E. that satisfies 61 Cov (e) and E ||=||* v
7. Let g be a function that satisfies (52) and (53). Then, for arbitrary fixed real vector I E IR" we have
Cov (o(xx = (f²8- -LLdd - - I.
Proof of Lemma D.3. We first derive bounds on the th moment of ||a|| (i 1,2.).. By Jensen's inequality, we have
E [|el|]] E (161r))) s (1x [1e1r9) t sTb.
(58)
Using Jensen's 's inequality again, we obtain that
||]||| = (E [[=][]] रे.
(59)
Lastly, by the Cauchy-Schwartz inequality, that
[|e||)] < (B [[eer]] E [[eer]] t S
E
(60)
Note that by (55), we have
Vg(x) + _ 2 (2(
Cov [g(2 + +)]]
Cov [g(a +5) g(x)] Cov
(61)
Since E [=]
O, we can further decompose (61) as
Cov
Vg(z) .+ 2 (2(()))
1 [1](
(Vo(z) e+ 2 (z( - _ (01 (x,
]
=E Vg(x) E
2 [0((,))
1 (o((),)) - 1 - [0(0((1)))]
Vg(x)) Cov [E] Vg(x) + Vg(z) E s.
1 Cov [u (rr
Vg(z))
T
(62)
By Lemma D.2 and (57), we know the first term in (62) is lower bounded by
Vg(z) Cov [s] Vg(x) ż 28T
(63)
Define the residual term as the sum of the last 3 terms in (62):
(Euleere)
-
1 [
R = Vg(x)- - E
1 - [0ln((e)))) .8"
1 Cov Cov (x)
+ E
2 21
(I,
Vg(x)T
(64)
To show Lemma D.3, we only need to show
||]|| S 2Le .7 ldd.
(65)
To this, note that
th (I, - 1 101
Vg(x)
[V(x))]
E E ( Ui (1(
E [2 (1,
(66a)
37

---

[| [s (2, ||
[ [e]
Ie (x,,,)] I
(66b)
(E
[||e 0n (x)
+ | [e]]l
E pv (z. e)]l
(66c)
(E [|]=]]
1 (I, 8)
+ E |||
E
(2,
(66d)
LLva
(E
||
|
[Iel|]
E [|e|1]]
(66e)
2
< Led. 7
(66f)
where we use the definition of the induced matrix norm in (66a); we use (52) and the triangle inequality in (66b); we use the Jensen's 's inequality and the definition of the induced matrix norm in (66c) and (66d); we use (56) in (66e); we use the bounds on the moments of ||e]| (58), (59), and (60)
in (66f).
On the other hand, we know that Cov (o] (ar, e)] is positive semi-definite matrix that satisfies
Cov (x1 s)] = E [ol (x, ] [1 (z, s)] E [v, [)]"
Thus, its induced matrix norm can be upper bounded by
||Cov (2, e)]1| - || (x)
|| < E [[] (2,,) (2, II] s E [Ien(x,=)IP)
Using the bound of ||li [x)= in (56) and the 4 th moment bound of ||=||, we obtain that
Cov [v1 (x)))]l < d [|=|*]] S Ct...
(67)
Note that the norm of R (Equation (65)) can be upper bounded by the sum of the norms of the separate terms. Thus, by combining the (66) and (67), we see that (65) holds.
n
Lastly, we consider the case when the input g can be expressed as the sum of sequence of mutual independent random vectors.
Lemma D.4. Let {XilsssN be a sequence of mean-zero random vectors in R&d that are mutually independent and satisfies 8I 3 Cov [X,) and E [|xx11]] S 7. Let g be a function that satisfies (52)
and (53). Then, for any positive integer N, we have
N
Cov
Σ
X2
=
(7'0-2146 2L08 .7 - -dd))
(68)
Proof of Lemma D.4. We use an induction on N to show that (68) holds.
When N = 1, (68) holds by setting œ = and s X1 Lemma D.3.
Suppose (68) holds for N- - 1. Then, for N, by the law of total variance, we see that
N
N
N
Cov
Σ X2
Cov
E
g
Σ
X
Σ
X
+
Cov
g
Σ i=1
X2
Σ X
1=1
(69)
For the first term in (69), we define a new function
g(z)= = E lø(x + Xx)]
Since the random variables IXihsis
mutually independent, we observe that
-
Σ X 0
N-
E
g
Σ Σ
x.
Σ x
One can verify that if g satisfies the conditions in (52) and (53), then also satisfies the same conditions as g because
(g g(2')l E 10(0 XN) g(2' + Xx)]ll < E [1 + +Nn) g(aa +xx)ll L/ z'Il.
38

---

On the other hand, we have
(g(x) 9(='), -x') x²)== (B (1 + XN) - g0 + X
= =Bgo( + XN) - x
For the Hessian upper/llwer bounds, because (T)( V 10 Xx) EV Xw)].
fl 1 (x)) = LI.
Therefore, by the induction assumption, we see that
N Σ
Cov
E g
X
X,
Cov
9
X,
i=1
= (N-1) 1) (7'5
2Led .72 Ld7)
(70)
For the second term in (69), we note that for any realization of 2i Xi. we have
N
N
N-1
Cov
Σ
X;
Σ f=1
X;
x = Cov (N)) Σ
Xi = x = Cov [gvl + Xx))
i=1
i=1
= (72 (728- -Led
न 1. 1,
where the conditioning be removed in the second step because the random variables {Xi) are mutually independent, so g(x + Xy) is independent with NN-1 X;; and we use Lemma D.3 in the last inequality. Therefore, we obtain that
N-1
Cov
y
Σ x,
= (7/6 2Led -
-
(71)
Substituting (70) and (71) into (69) shows that (68) still holds for N. Thus, we have proved Lemma D.4 by induction.
Now we come back to the proof of Theorem D.1. By the assumption, we know the distribution of X is identical to the distribution of Σ X,, where X; are i.idd random vectors that satisfy
E
X |I
< C- - 2 Thus, we have
N Σ
Cov [g(x)] = Cov g
X
Note that each X, satisfies Cov [X,] = 1. Cov [X] 2 # Applying Lemma D.4 gives that
Cov [g(X)] [1n2
33/4
2Led
..dd)
C N (.e)).1
VN
By letting tend to infinity in the above inequality, we finish the proof of Theorem D.I.
E Roadmap to Multi-step Prediction under Well-Conditioned Costs
A limitation of Assumption 4.7 in Section 4.1 is that it only allows the prediction V+(0) to depend on the disturbance W, at time step A natural question whether we can relax the assumption by allowing (0) to depend on all future disturbances WI: In this section, we present roadmap towards this generalization and discuss about the potential challenges.
First, we show that the expected cost-to-go function E [CT" (z; E) [.) can be expressed as function that only depends on the conditional expectations we for all 2 1, i.e., there exists function Ōr"" that satisfies
OF (z;; Wi = [CT (x; [(00]
(72)
39

---

We show (72) by induction on t= T,T 1,,,,,,........... 1,...,0. O. Note that the statement holds for T. Suppose it holds for + I, by (34), we have
8 (x We W 3) 1.(0) (2; E
Č (xr W, Wi:: W (1)4))))))) I.(0)]
where we use the induction assumption in the last equation. Define the random variables efe == W, Wa and 7/c = W + W Using the properties joint Gaussian distribution, we know that e ((j- are independent with (0). Therefore,
7z E
[ Ebe W ((+))----)I + (( 1[(0)]
B cer
e/p W (((+D)---)ee + -1
Thus, (2; can be expressed a function of and W (1)): and we denote it as
Č++1(#; W
((+1))r-111) = C (2; (z;
(73)
Therefore, we obtain that
c (x;E) 4.(00] = lif (x) + (- Oit1) w.f hi (x) + ( C 1 + WiR: w ((+))
Therefore, E CT (x;
also be expressed in the form C (z; W (e(r-)))) Thus, have shown (72) by induction, with (73) as an intermediate result. Note that the optimal policy is given by
I((0)]
T. (x: [())) == arg min u
(w) + (Apr + B.u + W ((0)))
arg min
(w) + Č, (Apr + Buu + W a/s w ((+
u
(wyO-n Oz" (A,r + W w (1))))
Therefore, by Lemma C.3, we need to establish covariance lower bound of the gradient
V. + WH w ((+)))T-1).)
in order to derive lower bound for the trace of the covariance matrix of л (x; (0)). While this relatively straightforward when we only have W because it is added directly with æ, is much more challenging to also consider the covariance caused by W (++1):(T-)]-- This is because they
affect Č, through multiple steps of infimal convolutions. Nevertheless, we feel the approach that we describe here is promising if we can derive more properties that are preserved through the infimal convolution operators. We leave this direction future work.
40


Reviews:
[{"review_id": "hF6sx1RwJe", "reviewer": "Reviewer_BHpD", "summary": "This paper introduces a new framework for analyzing stochastic online control with prediction. Because prior literature only considered pessimistic settings on the potentially stochastic predictions, the the main contribution of this paper is to analyze a much more general class of parametric predictions. With this new framework, the authors introduced a notion \"prediction power\" and later showed that this is stronger than a simple measure on the accuracy of the predictions.\n\nThis paper discussed two applications of the new framework:\n1. This paper first considered a linear time-varying dynamics with quadratic costs. Given the prediction framework, the resulting solution (at a high level) is a blend of the Riccati equation and Bellman equation.\n\n2. Then, this paper discussed a general setting where the Q functions and optimal policies satisfy certain mild assumptions. Examples were given to justify these assumptions.", "questions": "see above", "limitations": "see above", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I find this paper to be well-written and I especially appreciate the level of rigor displayed in Section 2. The theoretical contributions are also solid that they convincingly extended the analysis on the significance of predictions in online control. I really appreciate that the settings of this paper are both very general and well thought-out that they do not come across as sounding artificial.\n\nHowever, the notations of this paper are quite dense. In particular, the usage of uncommon Greek letters (e.g. $\\Xi$ and $\\iota$) may through many readers off. Also, the distinctions between $\\xi$ and $\\iota$ could be clarified.\n\nQuestion: In equation (3), shouldn't $Q$ and $C$ also depend on the particular realization $\\iota$? Or you meant to denote them as random functions whose randomness come from $\\iota$?\n\nSuggestions:\n- I feel the MPC formulation around equation (7) is quite interesting, but this part needs more discussion for the readers to understand the principles behind this formulation. Maybe you should consider moving parts of Appendix A.3 to the main body.\n- My feeling is that the proof techniques used in this paper are on the more standard side, but if there are any clever tricks being employed, I feel they should be highlighted in a proof sketch.\n- I feel that given examples and results are too much on the abstract side and I would like to see more concrete applications. In particular, I would like to see how the baseline prediction and the prediction parameter space are defined for a relevant problem.\n\nMinor concerns:\n- On line 209, I believe that $w^\\theta$ should be $v^\\theta$ instead?\n- On line 222, there is a naming collision between the sequence of (disturbance, prediction) pairs and the identity matrix.\n\nOverall, I think the paper makes a solid contribution to the literature. However, I am a little hesitant to give higher rating right now because the paper is very dense in notation but somewhat lacking in practically. It may be difficult for readers to fully appreciate the results. I will recommend a **borderline accept** right now, and reserve the possibility to raise my rating if the authors could adequately address my concern and justify the practical relevance of their work with more concrete examples.", "was_revised": true, "final_justification": "The overall technical contributions of this work is solid. And the author's rebuttal clarified most of my questions. But I am still afraid that the notation of the paper is inherently too cumbersome to be accessible for a wider audience. Therefore, I will maintain my original rating while being supportive of this paper's acceptance.", "rebuttal": "Thank you for your comments! Please find our response below.\n\n- _The distinctions between $\\xi$ and $\\iota$._\n\n$\\xi$ is the realization of the problem instance $\\Xi$ that contains all disturbances and predictions for all time steps $0, 1, \\ldots, T-1.$ $\\iota_t(\\theta)$ is the realization of the history $I_t(\\theta)$, which contains all past disturbances and predictions that are observed until an intermediate time step $t$. We will add a combined explanation of $(\\xi, \\Xi, \\iota_t(\\theta), I_t(\\theta))$ in the revision, because they are used frequently in our paper.\n\n- _How $Q$ and $C$ functions in (3) depend on the particular realization $\\iota_t(\\theta)$._\n\nWe define our instance-dependent $Q$ function and the cost-to-go function $C$ based on the problem instance $\\Xi$. Therefore, the $Q$ and $C$ values are determined by the specific realizations $\\xi$ of $\\Xi$ (see Eq. (3)). Since the history realization $\\iota_t(\\theta)$ is a part of the problem instance realization $\\xi$, our $Q$ and $C$ functions depend on $\\iota_t(\\theta)$ but are not decided by $\\iota_t(\\theta)$. To recover the classic definition of $Q$ and cost-to-go functions, one can take the conditional expectations of them given the history $\\iota_t(\\theta)$.\n\n- _Moving parts of Appendix A.3 to the main body._\n\nThanks for providing this suggestion! We will move (21) and some discussions from Appendix A.3 to the main body to further clarify what is “planning according to the $w_{\\tau\\mid t}^\\theta$.”\n\n- _Highlighting technical novelties in a proof sketch._\n\nThank you for providing this suggestion! Here are some technical novelties that we would like to highlight in the revision. First, in Theorem 4.3, we decompose the task of bounding the prediction power for the whole horizon $T$ to the verification of two conditions at each intermediate time step $t$. Our proof takes inspiration from the performance difference lemma, but we adopt novel methods to bound the difference between cost-to-go functions with the conditional covariance of the predictive policy's actions. Second, to show Lemma 4.6 and Equation (14), we prove and use properties of infimal convolution (see (35) in Appendix C.1) to preserve strongly convexity, smoothness, and the covariance of the input functions or variables. Therefore, we can verify Conditions 4.1 and 4.2 through backward induction, while the optimal policy does not have a closed-form solution.\n\n- _Definitions of the baseline prediction and the prediction parameter space in a relevant problem._\n\nIn the adaptive video streaming problem, a controller determines which quality level of a video segment to download, aiming to optimize the user’s experience. The predictions are about the future network bandwidth within a lookahead window. The baseline ($\\theta = 0$) could be “no-prediction” (e.g., some classic methods are not planning-based.) Other candidates ($\\theta = 1, 2,\\ldots$) can be a classic exponentially weighted moving average predictor, an ML-based predictor trained on a specific dataset, and other alternative sources of predictions.\n\n- _On Line 209, $w^\\theta$ should be $v^\\theta$._\n\nSorry for the confusion. Here, we refer to using the predictions $v_t(\\theta)$ to compute $w_{\\tau\\mid t}^\\theta$, which is defined as the conditional expectation of future disturbances given the current history (see Line 176). We will add a pointer to remind the readers in the revision.\n\n- _Naming collision between the sequence of (disturbance, prediction) pairs and the identity matrix on Line 222._\n\nThanks for catching this! We will change the notation of the identity matrix to $\\mathbb{I}$ and add an explanation in the revision."}, {"review_id": "4zbTxphC91", "reviewer": "Reviewer_3PE9", "summary": "The paper studies the concept of prediction power and extends the analysis of the previous works by studying time-varying predictions with more general costs. The motivation is clear, and the paper introduces clear concepts. The analysis of the stated results follows from the well-known counterparts and offers good intuition in understanding the forms and implications of the results. The paper addresses some general cases where convex costs can be applied with stability conditions on the time-linear varying system. Applicability of the results and extensions for relaxed conditions are briefly discussed at the end and in the appendix.", "questions": "1.\tThe concepts of predictions in this work are presented rather general; however, many recent works are studying online prediction algorithms, also touching on the importance of multi-step predictions for better control performance. Can the authors please clarify these points, especially in the introduction, and relate their work to the existing literature studying online prediction algorithms? Can you adapt existing prediction methods into your framework? Can you give examples from the existing literature in the setting that you study?\n2.\tThe connection of the disturbance W and the realizations is not precise. It seems that w_t is the sampled version of W_t in each time instance, as the shorthands below (6) suggest; however notation sometimes seems inconsistent. What sort of structure and assumptions do you need on W or the underlying distribution? Is W allowed to have temporal cross-correlation? The Assumption 2.2 seems to circumvent most of the issues related to time correlation, but do you need any additional assumptions on the support of the distribution, martingale structures, etc.?\n3.\tDo you implicitly assume a distribution over W in Assumption 4.7? The distributions are not explicitly stated in the paper and could use a careful treatment to clarify the conditions throughout.\n4.\tThe parametric prediction vector is unclear in the way the authors present it. Based on the theta, the parameter of a prediction algorithm, we will have imperfect predictions as illustrated in the examples. In this case, is the prediction power guaranteed to be positive? Your zero-theta case seems clear in the linear case, but this is not clear for general V, as the form of V and requirements on the predictor are not well addressed. Does this have any further implications? Please clarify.\n5.\tExample 3.3 is interesting; however, the construction depends on the specific choice of the estimating function V. Can you make claims about what the same example looks like for standard estimators such as RLS or similar? Do you think the issue stems also from the lack of cumulative information in the estimator structure, in other words, a lack of memory in the estimator? Please comment.\n6.\tThe use of M-GAPS in the example is somewhat distracting. Could you provide at least some intuition on how the algorithm works for the reader to better understand the example? The notation of V(1) and V(2) is confusing in the example; consider improving it for readability.\n7.\tWhat assumptions are needed on h for Condition 4.1? Please elaborate.\n8.\tThe conditions in Assumption 4.5 are rather restrictive and somewhat unclear. Do you require the \\mu_A and \\mu_B to be positive? Do you think you can exchange the strong convexity and smoothness assumptions with growth rate assumptions that may be less restrictive?\n9.\tThe first step in A.2 (16) is not clear, please clarify.", "limitations": "There is a brief discussion of limitations. However, the applicability of the results to time-varying examples are not shown and the authors do not provide clear claims of settings that satisfy their assumptions.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: Overall, the paper is well-constructed, and the concepts are clear. The authors propose a concept extending the existing literature and analyze it under reasonable settings with a thorough analysis. The results and the theoretical analysis offer good intuition and follow from well-known counterparts in the literature. The simple examples for the different settings and counterintuitive concepts help the reader understand the situation better, which strengthens the paper overall. \n\nClarity: The language of the paper is good and clear. Overall, the paper is well constructed, but some of the arguments are not very easy to follow due to the notation overhead and a few definitions that are not explicitly given. Please consider the notational clarity of the paper and especially the time indices of the time-varying arguments. Some of the concepts are not well-defined, such as the predictor class and the setting of the disturbances. Further clarity about these will help the reader.\n\nSignificance: The results offer insights into the use of the power of predictions in the time-varying setting with general costs. The theoretical results are all somewhat expected, and most examples are given for time-invariant cases with quadratic costs (even linear), even though the paper claims its novelty in time-varying cases. Showing simulation examples for the nonlinear or at least linear time-varying cases with general costs would certainly improve the significance of the paper. Limitations of the work are not well outlined.\n\nOriginality: The paper is largely inspired by the previous literature in [1]. The formal treatment of the power of predictions and the setting of the paper are original. However, many of the developments seem incremental with respect to the existing works in the literature and a reorganization of results rather than new ones. The authors should better highlight the originality beyond the power definition and time-varying adaptations of existing results.", "was_revised": true, "final_justification": "The authors provided good responses to the points I raised. The suggested revisions will improve the paper. The authors provide satisfactory clarifications and explanations to the unclear points in the text. The authors also consider potential future directions and discussing their framework in the context of common prediction methods. I improve my initial score accordingly.", "rebuttal": "Thank you for your comments! Please find our response below.\n\n- _Key differences between our work and the previous literature in [1]._\n\nWe respectfully disagree with the reviewer's point regarding the originality and would like to highlight several key novelties of our work in comparison to [1]. First, the misalignment issue between prediction power and accuracy (Section 3.1) would not exist under the exact-prediction setting in [1]. Second, discussing the connections with online policy optimization (Section 3.2) only makes sense in our setting, because the optimal predictive policy in [1] is fixed and known even when the distribution of the disturbances is unknown. Third, we extend our proof framework beyond the LQR setting in Section 4, while the proof techniques in [1] rely on the closed-form solutions of LQR. To address the challenge, we develop a novel proof framework in Theorem 4.3, which reduces the problem of comparing two policies on the whole horizon $T$ to verifying conditions about each individual policy at every intermediate time step $t$. Further, we prove and use the properties of infimal convolution (see (35) in Appendix C.1) to preserve strongly convexity, smoothness, and the covariance through backward inductions, which are critical for bounding the prediction power when closed-form solutions do not exist.\n\n- _Relationship with online prediction algorithms and how to adapt them._\n\nOnline prediction algorithms study methods for making predictions. In contrast, our work focuses on the process of using various forms of predictions to decide control actions. For example, uncertainty quantification (UQ) has recently received significant attention in the field of online prediction algorithms, providing not only point estimates but also confidence intervals. To use UQ as the predictor in our framework, the prediction $v_t(\\theta)$ should be the output of UQ at time $t$, including both the point estimate and the confidence interval.\n\n- _Clarifications about the distribution of $W_t$, the temporal cross-correlation, and the underlying assumptions._\n\nWe would like to clarify that we never assume $W_t$ is an independent distribution. Instead, all disturbances and predictions (i.e., the problem instance $\\Xi$) follow a joint distribution. In other words, conditioned on the realizations of past disturbances and predictions, the distribution of $W_t$ may change. We need Assumption 2.2 about $\\Xi$, which means its sampling cannot be affected by the controller’s states/actions. For example, the weather and its forecasts do not change because a person goes outside. Under Assumption 2.2, the disturbances and the predictions at different time steps can have correlations.\n\n- _Implicit assumptions about the distribution of $W_t$ in Assumption 4.7._\n\nThere are no implicit assumptions. We explicitly state the distribution of the pair $(W_t, V_t(\\theta))$ at each time step in Assumption 4.7. Since different time steps are independent, you can derive the distribution of $W_{0:T-1}$ from Assumption 4.7, which is a joint Gaussian distribution without temporal correlations.\n\n- _Clarification about the sign of the prediction power and the parametric form of the predictions._\n\nWhen the baseline predictor is no prediction, the prediction power is guaranteed to be non-negative. This is because the optimal policy for the no-prediction case is also a predictive policy when predictions are available, i.e., the controller can simply ignore the predictions. But the prediction power could be zero, for example, when the predictions are independent of the disturbances. We will clarify this in the revision.\n\nWe do not require the prediction $V_t(\\theta)$ to have any specific form as a function of $\\theta$. Generally speaking, $\\theta$ is primarily used for distinguishing different predictor candidates. Additional assumptions on the form of $V_t(\\theta)$ may be necessary for future directions, such as optimizing the prediction power $P(\\theta)$ as a function of $\\theta$ (Section 5).\n\n- _The specific choice of function $V_t(\\theta)$ in Example 3.3._\n\nThe intuition behind Example 3.3 does not require a very specific choice of the function $V_t(\\theta)$: The underlying idea is that the MSEs of estimating each individual entry of the multi-dimensional disturbance $W_t$ are insufficient to decide the prediction power. The off-diagonal entries of the covariance matrix $\\mathrm{Cov}[W_t \\mid V_t(\\theta)]$ also matter, and their impact on the prediction power depends on the specific dynamics $(A, B, Q, R)$. Therefore, a general accuracy metric (like MSE) that is unaware of $(A, B, Q, R)$ can be misaligned with the prediction power. We hope this intuition is convincing, and we will add more discussion in the revision.\n\n- _Applying estimators (with memory) on top of the provided prediction vector $V_t(\\theta)$._\n\nUnder our definition, the prediction power does not increase if one replaces the original prediction $V_t(\\theta)$ by any function of the history $I_t(\\theta)$, because this additional step cannot increase the information available at time step $t$. Indeed, since we do not require any particular form of the decision-maker, the predictive policy class $\\pi_t$ (Definition 2.3) is general enough to allow using filters like RLS as an intermediate step for deciding the control actions.\n\n- _Intuition behind M-GAPS and the notations $V_t(1), V_t(2)$ in Example 3.4._\n\nIntuitively, M-GAPS works by taking the gradient of the cost function with respect to the policy parameters at every time step, and it takes gradient steps to update $\\Upsilon_t$, allowing it to converge towards the optimal policy parameters under certain assumptions. Our goal is to highlight the connection between prediction power and online policy optimization, so the specific online policy optimization algorithms and their proofs are not the primary focus here. We will add more intuition in the revision.\n\nAs we mentioned before, the prediction parameters “1” and “2” here are used solely to distinguish between different predictors. We will clarify this in the revision.\n\n- _Assumptions on $h_t$ for Condition 4.1 to hold._\n\nCondition 4.1 does not impose explicit assumptions on the stage cost function $h_t$. However, since $Q$ and $C$ functions depend on $h_t$, structural assumptions about $h_t$ are necessary to establish Condition 4.1. An example is Assumption 4.5, which assumes that $h_t$ is both strongly convex and smooth for every time step $t$.\n\n- _The signs of $\\mu_A$ and $\\mu_B$ in Assumption 4.5._\n\nThanks for pointing this out! $\\mu_A$ does not need to be strictly positive, but $\\mu_B$ does. This is because the prediction power can be zero if $\\mu_B$ equals zero (see Theorem 4.8). We will clarify this in the revision.\n\n- _Exchanging the strong convexity and smoothness assumptions with more general growth rate assumptions._\n\nThanks for suggesting this direction of further generalization! We believe the quadratic growth/positive-definite covariance matrix conditions are natural generalizations of the LQR setting in Section 3. Following the intuition of Figure 3, we believe that further generalization of the growth rate condition in Condition 4.1 is possible if one can find the corresponding \"variance\" condition (i.e., the counterpart of Condition 4.2). This is an interesting future direction.\n\n- _Clarification about the first step in Appendix A.2 (16)._\n\nThank you for catching this! The equation holds because the cost-to-go function $C_t^{\\pi^\\theta}(x; \\xi)$ can be expressed as $Q_t^{\\pi^\\theta}(x, \\pi_t^\\theta(x; \\iota_t(\\theta)); \\xi)$. Substituting the expression of $\\pi_t^\\theta(x; \\iota_t(\\theta))$ into the expression of $\\mathbb{E}[Q_t^{\\pi^\\theta}(x, u; \\Xi)\\mid I_t(\\theta) = \\iota_t(\\theta)]$ in Proposition 3.1 gives (16) in Appendix A.2. We will add this clarification in the revision."}, {"review_id": "PUS1wlw7Bg", "reviewer": "Reviewer_v1xq", "summary": "This paper develops a mathematically grounded framework for quantifying the value of predictions in control, building on and extending the notion of prediction power introduced in [1]. The authors motivate the need for such a measure by showing that standard notions of prediction accuracy do not fully capture the impact of predictions on control performance. In particular, they demonstrate that the structure of the predictor can influence the optimal policy even when its accuracy is fixed. The paper is technically dense but includes illustrative examples that clarify the main contributions. Overall, it provides an interesting perspective that seems overlooked in much of stochastic optimal control: the idea that accuracy is not sufficient on its own may be relevant beyond the scope of this work.", "questions": "- Does the agent (i.e., the policy) have access to the system dynamics $f$? If so, and if the state $X_t$​ and past inputs are observable, then under invertible dynamics the agent may be able to reconstruct the disturbance $W_t$​. Is this possibility excluded by assumption, or is there something I'm missing in how the disturbance remains unpredictable?\n\n- Are there any further assumptions on the predictors, particularly regarding their bias or statistical relationship to the true disturbances $W_t$​? For instance, are predictors assumed to be unbiased, or can they be arbitrarily structured?\n\n\n- Could the framework be extended to partially observed settings, where the policy does not observe the full state $X_t$​ but only a noisy or filtered version (e.g., through a Kalman filter)? This would bring the framework closer to standard formulations in stochastic optimal control.\n\n\n- How does the analysis generalize when disturbances and/or predictions are temporally correlated? Would the proposed definition of prediction power and its theoretical properties still hold? \n\n- It is possible that a less accurate predictor - in terms of mean squared error - could lead to better control performance, for instance by reducing the impact of noisy or biased predictions. Would such a case be compatible with the proposed framework, or does the definition of prediction power implicitly assume that more accurate predictions always improve performance?", "limitations": "the authors have addressed the limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The paper is generally well motivated. Despite its technical depth, it offers insights that extend beyond the formal mathematics and are relevant to a broader control audience.\n\n- The mathematical derivations are rigorous and clearly applied to illustrative examples, which help ground the theoretical claims.\n\nWeaknesses:\n\n- While the motivation is clear, the paper may be difficult to follow for readers without a solid mathematical background. Some sections could benefit from additional qualitative explanations or intuition to complement the technical derivations.\n\n- Condition 4.1 seems central to the theoretical results, but its applicability is not fully characterized. While it holds in standard LQR settings, the paper does not discuss whether and how a nonzero matrix $M_t$​ can be found in more general cases.\n\n- The paper focuses on fully observed state settings. It would be interesting to discuss how the results might extend to partially observed settings, where the policy only has access to a noisy or compressed observation of $X_t$​, as is common in stochastic control.\n\n- The paper does not provide a method to estimate or optimize $\\theta$. While this is acknowledged in the text, it might limit the immediate applicability of the results.", "was_revised": true, "final_justification": "The main concerns I raised in my initial review have been addressed thoroughly and satisfactorily in the rebuttal and subsequent discussion. The authors provided clear clarifications on the points I found most critical, and their explanations strengthened my understanding and appreciation of the work. I therefore maintain my positive assessment and confirm my recommendation for acceptance, as I believe the manuscript makes a solid and valuable contribution to the field.", "rebuttal": "Thank you for your comments! Please find our response below.\n\n- _Adding more qualitative explanations or intuitions._\n\nThank you for the suggestion! We will add more explanations in the revision based on the feedback from the review process.\n\n- _Applicability of Condition 4.1 beyond LQR_\n\nThank you for pointing this out! Since Condition 4.1 is about the Q and C functions, specific assumptions on the stage cost $h_t$ and the dynamics $g_t$ are required to verify it. We want to clarify that Condition 4.1 is more general than the LQR setting. For example, we show it holds under Assumption 4.5 in Section 4.1, which allows non-quadratic cost functions. We will add a clarification in the revision.\n\n- _Access to the dynamics and reconstruction of the past disturbances._\n\nYes, we assume the controller has full knowledge of the dynamical function $f_t$, while the disturbance $W_t$ captures the uncertainties in the dynamics. With linear dynamics discussed in Sections 3 and 4, the controller can reconstruct $W_t$ using the transition tuple $(x_t, u_t, x_{t+1})$. This does not affect our prediction power because we include past disturbances (until time step $t-1$) in the history $I_t(\\theta)$, which is available to the controller at time step $t$.\n\n- _Potential extensions to partially observed settings._\n\nThanks for pointing out this extension! We do not think there is a straightforward way to achieve this due to the need to distinguish the disturbances in the system dynamics from the noises in the observation model, and the function form of the optimal policy is hard to define because it depends on the whole history. We will add this point to Section 5 in the revision. \n\n- _Clarification about the bias and the structure of predictions._\n\nOur setting does not assume the prediction $V_t(\\theta)$ to have any specific form of relationship with future disturbances. And $V_t(\\theta)$ does not need to be an unbiased estimator of $W_t$ or any future disturbances.\n\nWe note that our Examples 3.3 and 3.4 may leave the false impression that $V_t(\\theta)$ must be some structured function (e.g., linear function) of $W_t$. However, our intention is to show how a general phenomenon like the misalignment between accuracy and the prediction power may occur with simple constructions. We will add a clarification in the revision.\n\n- _Applicability to temporally correlated disturbances and predictions._\n\nOur definition of the prediction power and the theoretical results (except Theorem 4.8 in Section 4.1) allow the predictions and the disturbances to have temporal correlations across different time steps. When the cost function $h_t$ is non-quadratic, we require stronger joint-Gaussian and independence assumptions (see Assumption 4.7) to establish Condition 4.2. However, we believe it is possible to relax them and provide a justification in Appendix E.\n\n- _Intuitions about why more accurate predictions might not improve the prediction power._\n\nFirst, we want to clarify that this is not because the more accurate prediction is noisy or biased. To see this, note that any prediction $V_t(\\theta)$ needs to pass through its corresponding optimal policy $\\pi_t^\\theta$ to decide the action. If needed, the function $\\pi_t^\\theta$ can help eliminate the bias and reduce the variance.\n\nPerhaps a simple example that analogs the intuition is computing $\\mathbb{E}[Y|X]$. If we replace $X$ with $X'=2X$, the variance of the input increases, but $\\mathbb{E}[Y\\mid X']$ remains the same. Back to our setting, the prediction power will not change if we replace the prediction $V_t(\\theta)$ with $2V_t(\\theta)$ because the optimal control policy $\\pi_t^\\theta$ changes correspondingly.\n\nSecond, we would like to provide an intuitive explanation of the idea behind Example 3.3: The key takeaway is that MSEs of estimating each individual entry of the multi-dimensional disturbance $W_t$ are insufficient to decide the prediction power. The off-diagonal entries of the covariance matrix $Cov[W_t|V_t(\\theta)]$ also matter, and their impact on the prediction power depends on the specific dynamics $(A, B, Q, R)$. Therefore, a general accuracy metric (like MSE) that is unaware of the costs/dynamics can be misaligned with the prediction power.\n\nPlease let us know if the above clarifications help, and we are happy to add them in the revision."}, {"review_id": "kuXi8PtvNc", "reviewer": "Reviewer_HNJA", "summary": "This paper considers a control problem where we have some externals way to obtain some predictions for the disturbances. The paper then defines predictive power as the improvement in control cost one gets by using the predictions vs ignoring them. The authors make the important observation that this goal is quite different from accuracy! They then derives closed form expressions for the simple LQR case. The paper also discusses promising ideas for extension beyond the basic LQR case.", "questions": "Can you comment on the connection with predict then optimize literature? There a similar distinction between the value of prediction for downstream task and usual measures of prediction accuracy is emphasized.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n+ Written well and motivates the problem nicely\n+ Timely problem: value of predictions for various downstream tasks is being actively studied as ML pervades all areas\n+ High level message that prediction power and accuracy are not the same will resonate with non-theory folks as well\n\nWeakness:\n- More connections with predict-then-optimize framework where similar issues arise would have been better", "was_revised": true, "final_justification": "The authors agreed to include a bit more discussion about comparisons to work on predict-then-optimize aka decision-focused learning problems. I continue to think this is a good paper and maintain my score.", "rebuttal": "Thank you for your comments! Please find our response below.\n\n- _Connection with predict-then-optimize literature._\n\nWe would like to point the reviewer to our section on Related Literature, where we specifically highlighted the connection of our work with the decision-focused learning (DFL) literature, which includes the \"predict-then-optimize\" setting. (We indeed cite the seminal \"Smart Predict, then Optimize\" (Elmachtoub and Grigas, 2022) as reference [14].) In our revision, we will clarify that \"decision-focused learning\" and \"predict-then-optimize\" are different terms that refer to the same idea.\n\nAs you mentioned, a key insight is that minimizing a standard prediction error (e.g., MSE) may lead to suboptimal downstream decisions. Thus, the loss function for training the predictor needs to depend on the downstream optimization task. This is similar to the insight behind our Example 3.3.\n\nA major difference between our work and typical predict-then-optimize literature, though, is that our controller must decide control actions sequentially in a dynamical system, where the predictions are revealed in an online process. The controller can also build its knowledge from past disturbances and predictions to infer future disturbances or the optimal control action. Therefore, our online setting presents unique challenges compared with making a one-shot decision for a classic optimization problem. For this reason, we also focus on the evaluation of a given predictor and leave an end-to-end optimization of the predictor parameter $\\theta$ as future work (see Section 5).\n\nWe will discuss this connection in the revision."}]

Author rebuttal:

Meta-review: This paper studies the notion of prediction power for disturbances in online control, motivated by a demonstrated gap between prediction accuracy and actual utility for control. The authors develop a rigorous theoretical framework, establish tight upper and lower bounds on prediction power, and provide conditions under which predictions meaningfully improve control performance. 

Reviewers agreed that paper is technically solid, and relevant to the NeurIPS community. Strengths include clear conceptual advance, rigorous proofs, and timeliness of the problem. Main concerns centered on heavy notation and readability, limited concrete examples, and closeness to prior work. The rebuttal effectively clarified assumptions, emphasized applications (e.g. video streaming), and highlighted technical novelties, which increased reviewer confidence. 

Overall, I recommend acceptance. The paper makes a strong theoretical contribution with potential impact in bridging prediction and control. The result is solid but not strong enough to merit a spotlight IMO.
Decision: Accept (poster)