Data-driven Acceleration of MPC with Guarantees

Technical Summary: Data-driven Acceleration of MPC with Guarantees

Problem Statement
Model Predictive Control (MPC) is a dominant framework for optimal control of constrained, high-dimensional dynamical systems. However, its reliance on iteratively solving receding-horizon constrained optimization problems online creates a computational bottleneck, often rendering it unsuitable for low-latency applications. While explicit MPC and neural network approximations have been proposed to accelerate control, they suffer from significant drawbacks: explicit methods often require costly projection schemes or struggle with nonlinearities; neural networks are difficult to adapt to new data without retraining; and many nonparametric methods lack rigorous, non-asymptotic guarantees on feasibility and performance.

Methodology
The authors propose a novel, data-driven framework that accelerates MPC by replacing online optimization with a nonparametric policy constructed from offline MPC solutions. The core methodology involves three main components:

1. Offline Conservative Problem Formulation: Instead of solving the original MPC problem online, the authors solve a slightly more conservative version offline. This involves shrinking the state constraint set $X$ to an $\epsilon$-eroded set $X_{-\epsilon}$ (using the Pontryagin difference). Solving this conservative problem ensures that optimal trajectories remain strictly interior to the original constraint boundaries, providing a safety margin.
2. Nonparametric Policy Construction: A dataset $D$ is constructed from offline solutions, consisting of tuples $(x_i, u_i, J_i)$, where $x_i$ is a state, $u_i$ is the optimal control, and $J_i$ is the optimal cost-to-go for the conservative problem. The proposed policy $\pi_D$ is a greedy, nearest-neighbor rule: for a current state $x$, it selects the control $u_i$ associated with the dataset point $x_i$ that minimizes the regularized cost $J_i + \lambda \|x - x_i\|$.
3. Theoretical Guarantees: The authors establish conditions under which this policy is recursively feasible and admits a bounded optimality gap.
   • Recursive Feasibility: By leveraging the Lipschitz continuity of the system dynamics, the authors prove that if the dataset $D$ forms a sufficient cover of the state space (specifically, an $\epsilon/L_f$-cover), the policy remains feasible for the original, non-conservative problem.
   • Bounded Suboptimality: Using the Lipschitz continuity of the cost-to-go function, the authors construct data-dependent upper and lower bounds on the optimal cost. They prove that with a sufficiently large regularization parameter $\lambda$, the policy's cost is bounded above by a conservative upper bound derived from the data. This leads to a provable bound on the relative suboptimality gap, which tightens as the dataset coverage improves.

Key Contributions
The paper makes four primary contributions:

1. Novel Nonparametric Policy: A policy that approximately solves MPC problems using offline data from a conservative formulation, avoiding the need for online optimization.
2. Continual Learning Capability: The policy supports the incremental addition of new offline solutions without retraining. New data modifies the policy locally, enabling continual improvement.
3. Rigorous Theoretical Bounds: The establishment of explicit conditions on offline data coverage that guarantee recursive feasibility and bounded optimality gaps over the entire domain. These conditions define a clear trade-off between the amount of collected data and the tightness of the performance bounds.
4. Efficient Implementation: The policy is implemented as a lookup rule (using k-nearest neighbors via FAISS), which is orders of magnitude faster than solving MPC online.

Experimental Results
The authors validate their approach on two benchmarks: an inverted pendulum and a minimum-time unstable LTI system.

• Speed: The proposed policy (labeled MINT) achieves inference speeds between 100 and 1000 times faster than standard online MPC.
• Performance: The method demonstrates a favorable trade-off between latency and optimality. With sufficient data coverage, the policy achieves a relative optimality gap comparable to standard MPC with shorter lookahead horizons, while significantly outperforming those shorter-horizon MPCs in terms of solution quality.
• Verification: An algorithm based on sequential splitting of the state-space domain (Algorithm 2) is demonstrated to recursively verify feasibility and optimality certificates, confirming that the theoretical conditions are met in practice.

Significance and Claims
The authors claim that this work bridges the gap between the speed of explicit/nonparametric control and the rigorous guarantees of optimization-based MPC. Unlike neural network approaches, the proposed method does not require retraining for new data and offers non-asymptotic guarantees. The framework explicitly quantifies the trade-off between data collection effort (memory and offline computation) and control performance (optimality gap and feasibility). The results suggest that this approach is a viable candidate for real-time control tasks where low latency is critical, provided that sufficient offline data can be collected to satisfy the coverage conditions. The paper concludes by noting that future work will focus on scaling these methods to high-dimensional systems and embedded applications.