(434b) On the Performance of Stochastic Predictive Control

The computation of optimal decision policies for sequential decision-making under uncertainty has been recognized as a challenging problem [1]. Unless there exists a certain desired structure (e.g., [2]), the decision-making problem needs to explicitly account for every possible realization of uncertainty, which is typically expressed in the form of scenario trees. This gives rise to multi-stage stochastic programs [3,4], which become quickly intractable as the horizon length is extended due to the exponentially growing size of the scenario tree.

In the context of online control, the intractability of multi-stage stochastic programs is typically addressed by a stochastic predictive control framework (SPC; also called rolling-horizon heuristics in the operations research literature) [5,6]. In SPC, the full multi-stage problem is sought to be approximately solved by using a sequence of multi-stage stochastic programs with truncated prediction horizons. In each time stage, a truncated multi-stage problem is solved and the solution is actuated in a receding-horizon fashion. In this way, we attempt to mimic the behavior of optimal decision policy using a sequence of truncated-horizon decision policies. This method is becoming increasingly popular in different control applications, such as battery storage control [7], HVAC system control [8], and microgrids [9].

The SPC framework is designed based on the belief that the control policy implicitly defined by truncated stochastic control problems closely approximates the optimal decision policy. This belief perhaps originates from the empirical observation for deterministic model predictive control that the performance loss caused by truncation vanishes as the prediction horizon is extended [10]. However, such a belief is not adequately substantiated by means of rigorous analysis. Even for deterministic settings, it has only been recently proved to be true [11]. This motivates an important open question: What is the price of truncating the prediction horizon in SPC?

We aim to address this question by analyzing the dynamic regret of SPC for linear systems with quadratic performance index and additive and multiplicative uncertainty. In particular, we characterize the relationship between the performance loss caused by truncation and the prediction horizon length. Under robust stabilizability and detectability assumptions, we show that the performance loss compared to the optimal policy decays exponentially in the prediction horizon length. This result rigorously substantiates the belief that an SPC scheme with a sufficiently long prediction horizon closely approximates the optimal policy. That is, SPC can provide a near-optimal control policy, in the sense that one can make its performance arbitrarily close to that of the optimal policy. The technical results are built on the recently established property of graph-structured optimization problems called exponential decay of sensitivity [12,13].

[1] Birge, J. R. (1985). Decomposition and partitioning methods for multistage stochastic linear programs. Operations research, 33(5), 989-1007.
[2] Theil, H. (1957). A note on certainty equivalence in dynamic planning. Econometrica: Journal of the Econometric Society, 346-349.
[3] Pereira, M. V., & Pinto, L. M. (1991). Multi-stage stochastic optimization applied to energy planning. Mathematical programming, 52(1), 359-375.
[4] Shapiro, A. (2006). On complexity of multistage stochastic programs. Operations Research Letters, 34(1), 1-8.
[5] Lucia, S., Finkler, T., & Engell, S. (2013). Multi-stage nonlinear model predictive control applied to a semi-batch polymerization reactor under uncertainty. Journal of process control, 23(9), 1306-1319.
[6] Bernardini, D., & Bemporad, A. (2011). Stabilizing model predictive control of stochastic constrained linear systems. IEEE Transactions on Automatic Control, 57(6), 1468-1480.
[7] Kumar, R., Wenzel, M. J., ElBsat, M. N., Risbeck, M. J., Drees, K. H., & Zavala, V. M. (2020). Stochastic model predictive control for central HVAC plants. Journal of Process Control, 90, 1-17.
[8] Kumar, R., Wenzel, M. J., Ellis, M. J., ElBsat, M. N., Drees, K. H., & Zavala, V. M. (2018). A stochastic model predictive control framework for stationary battery systems. IEEE Transactions on Power Systems, 33(4), 4397-4406.
[9] Hans, C. A., Sopasakis, P., Bemporad, A., Raisch, J., & Reincke-Collon, C. (2015, December). Scenario-based model predictive operation control of islanded microgrids. In 2015 54th IEEE conference on decision and control (CDC) (pp. 3272-3277). IEEE.
[10] Morari, M., & Lee, J. H. (1999). Model predictive control: past, present and future. Computers & Chemical Engineering, 23(4-5), 667-682.
[11] Lin, Y., Hu, Y., Shi, G., Sun, H., Qu, G., & Wierman, A. (2021). Perturbation-based regret analysis of predictive control in linear time varying systems. Advances in Neural Information Processing Systems, 34.
[12] Shin, S., Anitescu, M., & Zavala, V. M. (2021). Exponential decay of sensitivity in graph-structured nonlinear programs. SIAM Journal on Optimization (in press).
[13] Shin, S., & Zavala, V. M. (2021). Controllability and observability imply exponential decay of sensitivity in dynamic optimization. IFAC-PapersOnLine, 54(6), 179-184.