Sub-linear Regret in Adaptive Model Predictive Control
This work addresses control of uncertain systems with constraints, providing a theoretical guarantee for regret in adaptive MPC, which is incremental as it builds on existing methods like certainty-equivalence and polytopic tubes.
The paper tackles the problem of adaptive Model Predictive Control for uncertain linear systems with constraints, presenting STT-MPC, an online algorithm that achieves sub-linear regret of O(T^{1/2 + ε}) compared to an oracle aware of the system dynamics.
We consider the problem of adaptive Model Predictive Control (MPC) for uncertain linear-systems with additive disturbances and with state and input constraints. We present STT-MPC (Self-Tuning Tube-based Model Predictive Control), an online algorithm that combines the certainty-equivalence principle and polytopic tubes. Specifically, at any given step, STT-MPC infers the system dynamics using the Least Squares Estimator (LSE), and applies a controller obtained by solving an MPC problem using these estimates. The use of polytopic tubes is so that, despite the uncertainties, state and input constraints are satisfied, and recursive-feasibility and asymptotic stability hold. In this work, we analyze the regret of the algorithm, when compared to an oracle algorithm initially aware of the system dynamics. We establish that the expected regret of STT-MPC does not exceed $O(T^{1/2 + ε})$, where $ε\in (0,1)$ is a design parameter tuning the persistent excitation component of the algorithm. Our result relies on a recently proposed exponential decay of sensitivity property and, to the best of our knowledge, is the first of its kind in this setting. We illustrate the performance of our algorithm using a simple numerical example.