Carrying Scenarios Forward: Warm-Started Safety Certificates for Stochastic MPC

Controllers that plan under uncertainty often guard against random disturbances by sampling them. At every control step the planner draws $N$ random "scenarios" (possible future disturbance sequences or plausible system models) and requires the plan to stay safe in all of them. Scenario theory then states how large $N$ must be so that the plan violates its constraints with probability at most $\epsilon$, with confidence $1-\beta$. In practice these sample counts are far larger than needed. In Scenario-based Stochastic MPC for systems with uncertain dynamics, simulated violation rates stay well below $\epsilon = 0.1$ at scenario counts far below the theoretical prescription. The controller also discards all of its samples at every step and redraws them, even though consecutive problems are nearly identical. Model predictive control (MPC), which replans over a sliding time window at every step, already exploits this continuity on the optimizer side. Shifting yesterday's plan forward as today's starting point cuts solver iterations by large factors, as in Distributed Formation Control for Multi-Vehicle Systems With Splitting and Merging Capability and Closed-loop Analysis of ADMM-based Suboptimal Linear Model Predictive Control. No one has applied the same move on the statistical side.

We propose to warm-start the sample set, not just the solver. At each step the controller keeps the few scenarios that actually determined the previous plan (its "support" scenarios, the ones whose removal would change the solution), shifts them forward in time, and adds a small batch of fresh independent draws. Condition on the past and treat the carried scenarios as fixed, deterministic constraints. The current step is then an ordinary scenario program over the fresh draws alone, so standard theory applies without modification. The certificate depends only on how many fresh scenarios end up being support scenarios. Our hypothesis is that, because the system evolves smoothly, the carried scenarios already pin down most of the plan and very few fresh draws become support. That would let a much smaller per-step batch carry a valid certificate at the same $\epsilon$ and $\beta$.

Core Claim

The theory-practice gap in scenario-based MPC has two separable parts. The first is that classical bounds count every decision variable as a potential support constraint when only a handful ever bind. Existing a posteriori bounds already address this part by counting support constraints after solving, with no change to the algorithm. The second part is temporal redundancy: the controller repeatedly pays to rediscover the same binding scenarios at every step. Only reusing samples across time can remove this second part.

Concretely, let $N_f$ be the number of fresh scenarios drawn at step $t$ and $s_t^f$ the number of them that are support constraints of the solved program. Let $V(u_t)$ be the probability that the applied plan $u_t$ violates the constraints for a new disturbance draw. Let $\epsilon(s, N_f, \beta)$ be the standard a posteriori violation level, obtained from a binomial tail as a function of support count $s$, sample size $N_f$, and confidence parameter $\beta$. Conditioned on the history, the fresh draws are independent and identically distributed and independent of the carried ones, so

$$ \Pr\big[\, V(u_t) > \epsilon(s_t^f, N_f, \beta) \,\big|\, \text{history} \,\big] \le \beta . $$

This holds for convex scenario programs, whatever the carried scenarios are. The interesting question is empirical and structural: how small $s_t^f$ is under temporal continuity, and what the extra conservatism from the carried constraints costs in control performance. We expect $s_t^f$ to be near zero in steady operation and to spike only when the active constraints change, such as at the onset of an obstacle or a constraint boundary.

Relation to Prior Work

Two papers motivate the proposal. Scenario-based Stochastic MPC for systems with uncertain dynamics builds a scenario MPC for linear systems with additive noise and partially unknown dynamics. It samples models by bootstrapping past trajectories and documents the gap, but solves each step from scratch with fresh scenarios. We keep its problem class and controller and change only how scenarios are managed across time. Closed-loop Analysis of ADMM-based Suboptimal Linear Model Predictive Control shows the optimizer-side analogue of the gap. ADMM is a splitting algorithm that solves the problem in cheap alternating pieces, and in that paper it is warm-started by shifting the previous primal and dual variables. Theory requires $\ell^* = 85$ ADMM iterations per step for provable stability on a constrained double integrator, yet 23 to 30 suffice empirically. Its analysis is deterministic. We reuse its benchmark and its shifted-warm-start solver, and we add a stochastic disturbance.

Two papers constrain the design. Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gap proves that bias carried into a warm-started learner creates an error floor that further updates cannot remove. The analogous danger here is that carried scenarios drawn from a stale bootstrapped model keep shaping the plan after the model has improved. This is why our scheme gives every carried scenario an expiry rule and never counts it toward the certificate. Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-Start shows that warm-starting is unnecessary for optimal sample complexity in static contractive bilevel problems. We take this seriously. Our claim is not that warm-starting improves a convergence rate. It is that, in a time-varying problem, reuse reduces the number of fresh samples a certificate needs. If cold-start a posteriori bounds turn out to match carry-over, we will have reproduced their conclusion in the control setting, and that is a publishable negative result.

The diffusion-policy warm-start papers, Real-Time Iteration Scheme for Diffusion Policy and STEP: Warm-Started Visuomotor Policies with Spatiotemporal Consistency Prediction, shift the previous action plan and denoise only a few steps. They show the same continuity in a learned setting but carry no statistical certificate. We use them only to motivate why reuse failures cluster at moments when the plan changes discontinuously, and the racing work Constraint-Aware Diffusion Guidance for Robotics: Real-Time Obstacle Avoidance for Autonomous Racing reports exactly such local-minimum trapping under warm-starting.

Research Program

The method is simple to state. At step $t$, the controller takes the support scenarios from step $t-1$, drops their first time slice, and appends one fresh disturbance sample to each so they cover the new horizon. It discards any carried scenario older than a fixed age or drawn from a model posterior that has since been updated. It then adds $N_f$ fresh draws, solves, identifies support scenarios among both pools, and reports $\epsilon(s_t^f, N_f, \beta)$. There is also an adaptive variant: if the certified level exceeds the target, the controller draws more fresh scenarios and re-solves, so $N_f$ grows only at constraint-switching events.

The analysis has three parts. First, we will prove the conditional certificate above and extend it to the uncertain-dynamics setting, where fresh models are drawn from the current bootstrap distribution. Second, we will characterize when $s_t^f$ is small. For linear systems with polytopic constraints and a locally invariant active set, we expect fresh support counts to be bounded by the number of constraints that newly become active between $t-1$ and $t$. This would turn temporal continuity into a sample-count statement. Third, we will handle truncated solvers. Support identification assumes an exact solution, but real-time ADMM stops early. We will tighten constraints by a margin derived from the ADMM residual and check whether the certificate survives with 23 to 30 iterations, the empirically sufficient range reported by Srikanthan et al. This links the iteration-count gap in that paper to the sample-count gap in Micheli and Lygeros.

Baselines

The naive reference point is cold-start scenario MPC with $N$ set by the classical a priori bound, which depends on the number of decision variables, with fresh scenarios at every step. This is the standard practice whose conservatism defines the gap. It is run on identical systems, disturbance distributions, horizons, and $(\epsilon, \beta)$, and we report its per-step scenario count, solve time, closed-loop cost, and violation statistics.

The strongest existing method on this exact question is UD-SMPC from Scenario-based Stochastic MPC for systems with uncertain dynamics, together with its non-robust least-squares variant. The paper reports that the least-squares variant fails the $\epsilon = 0.1$ requirement in about 12% of trials, while UD-SMPC keeps violations within target. Per-$N$ violation percentages appear only graphically, and no reported numeric violation curve was found on Lacuna for UD-SMPC. We will therefore re-implement it on its own simulation setup and reproduce the roughly 12% least-squares failure rate as a sanity check before comparing.

The most important competitor is cold-start UD-SMPC with an a posteriori support-count certificate at the same $N_f$. It isolates the first component of the gap. Beating it means certifying the same $\epsilon$ at confidence $1-\beta$ with substantially fewer fresh scenarios per step, or the same fresh count with a tighter certified $\epsilon$. Two further conditions must hold: the closed-loop cost must stay within a few percent, and the fraction of Monte Carlo trials whose true violation exceeds $\epsilon$ must not exceed $\beta$.

Two ablations isolate the key ingredient. Solver-only warm-starting shifts primal and dual variables as in Srikanthan et al. but redraws all scenarios. It separates computational warm-starting from statistical reuse and should change solve time but not the certificate. Reuse without expiry tests the stale-bias failure predicted by the actor-critic analysis. All methods share a tuning budget for $N_f$, horizon, and expiry age, selected on held-out disturbance seeds.

Why not just…?

Why not just use a posteriori support-count bounds with cold starts? This is the real threat, since such bounds already remove the part of the gap caused by counting inactive decision variables. Our design makes it the headline comparison. If cold-start a posteriori certificates match carry-over at equal fresh-sample counts, the temporal-reuse claim is false, and we will report that the gap is fully explained by support counting. Carry-over can only win if fresh support counts under reuse are much smaller than support counts under cold start, which is precisely the quantity we measure.

Why not just draw a huge $N$ in parallel on a GPU? Differentiable Model Predictive Control on the GPU shows GPU solvers are fast, but its 4–7x speedups come from warm-starting across frames, not from brute-force cold starts. More importantly, larger $N$ makes certificates more conservative in closed-loop cost because more scenarios are enforced, and it does nothing to explain the gap. We will include a compute-matched large-$N$ cold-start run to show the resulting cost and solve-time trade-off.

Why not just tighten the concentration inequality on paper? A sharper bound for a single step cannot exploit information from the previous step, because the bound treats each step as an isolated problem. Srikanthan et al. found that their 85-versus-23 iteration gap came from the interaction between plant and optimizer, not from a loose inequality. We expect the same here, and the comparison against the a posteriori baseline, the tightest single-step certificate available, tests it directly.

Why not just warm-start the solver and leave sampling alone? This is our solver-only ablation. Shifting optimizer variables speeds up each solve but leaves the number of fresh scenarios, and therefore the certificate, unchanged. If this ablation closes the practical gap, the sample-side contribution is unnecessary.

Proposed Experiments

The first testbed is the uncertain-dynamics simulation of Micheli and Lygeros, with $\epsilon = 0.1$, scenario counts swept over a grid, and thousands of Monte Carlo trials. The second is the constrained double integrator of Srikanthan et al. with added bounded random disturbances, solved by warm-started ADMM truncated at 23, 30, and 85 iterations. On each, we measure four things. The first is true violation probability, estimated on independent large test draws per step. The second is the fraction of trials exceeding the certified $\epsilon$, which must stay at or below $\beta$. The third is fresh scenarios per step and wall-clock solve time. The fourth is closed-loop cost. We also log the per-step trace of fresh support counts $s_t^f$ against changes in the active constraint set.

Three checks decide the outcome. The first is validity: the fraction of trials exceeding $\epsilon$ stays at or below $\beta$ for carry-over with expiry, and is expected to break down without expiry when the bootstrap model shifts. The second is the headline: at matched $\epsilon$ and $\beta$, carry-over needs several times fewer fresh scenarios than cold-start a posteriori certification, and the reduction is concentrated in steps where the active set does not change. The third is truncation: with residual-based tightening, the certificate remains valid at 23 to 30 ADMM iterations, showing that the iteration gap and the sample gap can be closed by the same temporal argument. A stress test with abrupt constraint changes, such as a pop-up state bound, should show $s_t^f$ spiking and the adaptive variant drawing more samples exactly then. That behavior is the evidence that reuse tracks real structure in the problem and does not just hide risk.