On the suboptimality of stochastic MPC with varying constraint horizon

Allan Andre Do Nascimento; Andre Bertolace; Antonis Papachristodoulou; Kostas Margellos

Source-linked AI summary

On the suboptimality of stochastic MPC with varying constraint horizon

Allan Andre Do Nascimento, Andre Bertolace, Antonis Papachristodoulou, Kostas Margellos

arXiv:2608.30017v1Aug 30, 2026math.OCeess.SY

TL;DR

Full-horizon stochastic state-constraint enforcement can be costly, motivating MPC without terminal ingredients and with a shorter constraint horizon. The paper uses stochastic relaxed dynamic programming to derive an explicit horizon-dependent closed-loop cost bound, and gives a deterministic reformulation for a linear-quadratic setting with affine chance constraints and bounded uniform disturbances. The results characterize a trade-off in which shortening the constraint horizon tightens the bound but adds chance constraints, while simulations assess computational effort and performance.

Problem
The paper addresses stochastic MPC without terminal ingredients when enforcing probabilistic state constraints over the full prediction horizon is computationally demanding.
Method
The paper combines stochastic relaxed dynamic programming with finite-dimensional control parameterization and deterministic constraint tightening for the linear-quadratic case.
Results
The analysis derives an explicit upper bound on average expected closed-loop cost that depends on the prediction and constraint horizons.
Takeaways & Limitations
Decreasing the constraint horizon tightens the bound but adds chance constraints, so horizon selection exposes a computational-effort and performance trade-off.

Abstract

from arXiv · show

Enforcing stochastic state constraints over the full prediction horizon in Model Predictive Control (MPC) can be computationally demanding. Here we study stochastic MPC without terminal ingredients in which chance constraints are enforced only over a shorter constraint horizon. Using stochastic relaxed dynamic programming, we derive an explicit upper bound on the average expected closed-loop cost that depends on both prediction and constraint horizons. For linear quadratic problems with affine chance constraints and bounded uniform disturbances, we provide a deterministic reformulation via coordinate transformation and constraint tightening. Simulations illustrate the trade-off between computational effort and performance.

I. INTRODUCTION

The paper studies stochastic MPC without terminal ingredients when probabilistic state constraints are enforced over only part of the prediction horizon. It examines how prediction and constraint horizons affect average expected closed-loop cost while seeking reduced computational effort.

Problem formulation: The stochastic formulation uses i.i.d. disturbances, hard input constraints, and probabilistic state constraints with confidence level 1-ε.Chance constraints trade performance against controlled state-constraint violations, while hard input constraints represent actuator limits.
Motivation: Partial constraint enforcement is motivated by the expense of enforcing constraints at every prediction step and provides a computational-effort lever in disturbed stochastic systems.The paper extends prior variable-horizon ideas to stochastic MPC and derives an expression involving both horizons.
Motivation: Stochastic MPC without terminal ingredients is analyzed with a constraint horizon shorter than the prediction horizon.Probabilistic state constraints are imposed over the constrained portion, while the remaining terminal steps are unconstrained.
Controller structure: A finite-dimensional parameterization restricts the control mappings through state-independent optimization parameters, yielding a generally suboptimal class of control laws.The viability assumption provides well-posedness and recursive feasibility for the first applied input.
Objective: The study targets the average expected infinite-horizon closed-loop cost and its dependence on the prediction and constraint horizons.The resulting analysis provides performance bounds that can also support stability analysis.

III. MAIN RESULT

The main result uses stochastic relaxed dynamic programming to bound the average expected closed-loop cost of partially constrained stochastic MPC. The bound is explicit and reflects the distinct prediction and constraint horizons.

Stochastic closed-loop sub-optimality: Stochastic relaxed dynamic programming yields an upper bound on the average expected closed-loop cost under partially constrained MPC.The result applies for N ≥ 2 and 2 ≤ Ñ ≤ N under the stated viability and drift assumptions.
Explicit bound: The explicit bound is parameterized by α and c2, whose characterizations depend on the adopted control strategy.The bound is meaningful when α ∈ (0,1).

B. Explicit expressions for α and c2

The section constructs horizon-dependent value functions and uses stochastic relaxed dynamic programming to obtain explicit expressions for the suboptimality parameters α and c2. The resulting average expected closed-loop cost bound depends on disturbance costs, the constrained and unconstrained horizon portions, risk level, and cost-controllability assumptions.

Horizon-dependent value functions: Variable-constraint-horizon OCPs separate unconstrained tail problems from chance-constrained initial problems in the backward value-function construction.For n<˜N, minimization uses the unrestricted input-feasible set; for n≥˜N, chance constraints further restrict admissible controls.
Horizon-dependent value functions: The value-function decomposition separates running costs from the constrained and unconstrained portions of the prediction horizon.The constrained contribution covers predicted states and inputs satisfying probabilistic constraints, while the remaining contribution represents the unconstrained portion.
Explicit bound: The average expected closed-loop cost bound incorporates disturbance costs, constrained-part decay σ1^(N−˜N+1), and tail decay Σ_{j=0}^{˜N−1}σ2^j.The bound is meaningful only when α∈(0,1), and the risk level ε affects α and c2 through the feasible sets.
Horizon trade-off: Decreasing ˜N tightens the bound with other quantities fixed but adds chance constraints, while monotonicity is not guaranteed because the quantities depend on (N,˜N).The trade-off is therefore horizon-dependent rather than universally monotone.
Horizon trade-off: The explicit estimate may be conservative because of discarded terms, uniform cost-controllability estimates, and the max operator used in its construction.Trajectory-wise assumptions and tighter admissible constants or decay rates are identified as possible sources of improvement.

C. Reformulation of Partially Constrained MPC

The partially constrained stochastic MPC problem is reformulated deterministically for linear systems by separating nominal and deviation dynamics. Affine chance constraints are represented through nominal terms and error residuals under a stabilizing feedback parameterization.

Chance-constraint reformulation: The reformulation assumes each affine chance-constraint set is contained in the admissible state set, making the imposed conditional chance constraint sufficient for state admissibility.The stage cost is quadratic with Q,R>0, and g is affine.
Coordinate transformation: The control parameterization ui|k=vi|k+Kei|k uses decision variables vi|k and a feedback matrix K such that Acl=A+BK is Schur.The disturbance distribution is bounded, uniform, independent across components, and zero mean.
Coordinate transformation: The linear stochastic dynamics are decomposed into nominal dynamics and deviation dynamics using a coordinate transformation.The transformed system uses zi+1|k=Azi|k+Bvi|k and ei+1|k=Aclei|k+GWk+i with e0|k=0.

1) Cost function transformation:

The quadratic finite-horizon cost is transformed into nominal and disturbance-propagation components. Deviation covariance is propagated recursively under the closed-loop error dynamics.

Cost transformation: The quadratic finite-horizon cost is split into a nominal cost and a disturbance-propagation contribution.This decomposition follows the nominal/deviation coordinate transformation used for the deterministic reformulation.
Cost transformation: The transformed cost accounts for disturbance propagation through the covariance sequence generated by the closed-loop deviation dynamics.The recursion provides the covariance terms required by the deterministic MPC formulation.
Cost transformation: The deviation covariance starts at zero and evolves as Σe,i+1=AclΣe,iAcl^T+GΣWG^T.Here ΣW is the disturbance covariance and the recursion is applied at each prediction step.

2) Input Constraint Tightening:

Input constraints are tightened so that the feedback-corrected input remains admissible for every disturbance realization. The tightening is computed from recursively propagated deviation reachable sets.

Reachable deviation sets: Deviation reachable sets are generated by the Minkowski recursion E0={0}, Ei+1=AclEi⊕GW.Because ei|k∈Ei for all admissible disturbances, these sets bound the feedback-induced input deviation.
Tightened input constraints: The nominal input is restricted to Vi=U⊖(KEi), ensuring vi|k+Kei|k∈U for every ei|k∈Ei.The Pontryagin difference converts robust input admissibility into tightened nominal-input constraints.

3) State Constraint Tightening:

Affine chance constraints are decomposed into deterministic nominal terms and disturbance-dependent residuals, then enforced through quantile-based constraint tightening. The resulting tightened constraints form a deterministic MPC reformulation over the constraint horizon.

Constraint decomposition: Affine state constraints decompose into a nominal term and a scalar residual driven by propagated error and new disturbances.The residual is δ_i = (a^T A_cl + b^T)e_i|k + a^T G W_k+i.
Quantile tightening: Conditioning on the predicted state fixes the error, leaving only the new disturbance random; its quantile defines the tightening term q_i.The constraint becomes g(z_i+1|k,z_i|k) + q_i ≤ 0 for every admissible error realization.
Quantile tightening: The tightening combines the propagated disturbance-set contribution with the (1 − ε)-quantile of the new-disturbance term.For bounded independent uniform disturbances, the weighted-sum CDF is evaluated using the generalized Irwin–Hall distribution.
Scope: Uniformity and componentwise independence are needed for exact quantile evaluation, while the main results allow any distribution satisfying temporal independence.Distribution mismatch and temporal correlation are identified as outside the current treatment.
Alternative conditioning: Conditioning directly on x_k yields an exact complete-residual quantile, but the shifted candidate may become infeasible and requires additional analysis.The paper therefore distinguishes this alternative from conditioning on the predicted state.

IV. NUMERICAL SIMULATIONS

The simulations evaluate the proposed stochastic MPC formulation on a disturbed linear double integrator while varying the constraint horizon with a fixed prediction horizon. Repeated closed-loop experiments compare the trajectory-based suboptimality indicator with computational time.

System and disturbances: The experiment uses a stochastically disturbed linear double integrator with i.i.d. zero-mean uniform disturbances bounded by w_max = 0.01.The system state contains positions and velocities, while the disturbance contains x- and y-accelerations.
Simulation setup: Input constraints impose bounded accelerations with a_max = 5 in both coordinate directions.The admissible input set constrains each acceleration between −a_max and a_max.
Chance constraints: State chance constraints use two CBF candidates defining a forbidden position region, with violation levels ε_1 and ε_2 and γ = 0.8.A velocity constraint is also imposed with ε_3 = 0.05 and v_max = 2.
Chance constraints: Boole’s inequality splits the ℓ1 velocity constraint into four half-spaces, each enforced with probability at least 1 − ε_3/4.The resulting CDFs are evaluated using the generalized Irwin–Hall distribution.
Evaluation: For each fixed (N,Ñ), 100 repetitions produce boxplots of the estimated α̂ and computation time to assess the constraint-horizon effect.The quantities C_1,k and C_2,k are computed along each closed-loop trajectory, with σ_1 = 0.8 and σ_2 = 0.85 fixed.
Evaluation: The α̂ value is a trajectory-level a posteriori certificate only when α̂ ∈ (0,1); otherwise, no certificate is claimed.These estimates are not state-uniform estimates of Proposition 3.2’s theoretical constant.

V. CONCLUSION

The paper analyzes partial chance-constraint enforcement in stochastic MPC without terminal ingredients and derives a deterministic reformulation through constraint tightening. Simulations assess the resulting trajectory-based indicator and computational effort.

Conclusion: The work studies how partial constraint enforcement affects the closed-loop upper bound in stochastic MPC without terminal ingredients.The formulation uses a variable constraint horizon shorter than the prediction horizon.
Conclusion: A parameterized finite-dimensional stochastic MPC formulation is converted into deterministic MPC through coordinate transformation and deterministic chance-constraint tightening.This reformulation is developed for the stated stochastic MPC setting and supports computational evaluation.
Conclusion: Simulations evaluate the trajectory-based a posteriori α-indicator together with computational effort.The conclusion frames these evaluations as illustrations of the proposed analysis.

VI. APPENDIX

The appendix derives the average expected closed-loop cost bound by applying a one-step inequality, summing it over time, and using conditional expectations and telescoping. The resulting bound follows from comparing the value function with shifted suboptimal terms.

Bound derivation: The proof begins from a one-step inequality relating the value function, expected future value, and running cost.This inequality is applied along the closed-loop dynamics.
Bound derivation: Summing the inequality over m sequential steps produces a cumulative relation involving the initial and terminal value functions.The proof then conditions the relation on the initial state.
Average-cost bound: The tower property and telescoping convert the cumulative inequality into an average-cost bound after division by m and α.Continuity and compactness provide control of the remaining expected value-function term.
Value-function comparison: The running-cost decomposition separates terms under the chance constraint from inputs unaffected by it.The latter terms are bounded using a value function with length Ñ and a constrained first input.
Value-function comparison: The final comparison bounds the value function by selected shifted suboptimal inputs and auxiliary value-function terms.This comparison yields the stated bound in equation (32).

C. Proof of Proposition 3.2 “

The proof applies an assumption and prior inequalities to rearrange the bound and compare it with an earlier expression.

Assumption 3.1 is used on the right-hand side of (17).
The last inequality follows by using (18).
Rearranging the right-hand side produces the subsequent expression.
Expression (34) is compared with (9).