On-the-fly control of unknown nonlinear systems with sublinear regret

Abraham P. Vinod, Arie Israel, Ufuk Topcu

Abstract

We study the problem of data-driven, constrained control of unknown nonlinear dynamics from a single ongoing and finite-horizon trajectory. We consider a one-step optimal control problem with a smooth, black-box objective, typically a composition of a known cost function and the unknown dynamics. We investigate an on-the-fly control paradigm, i.e., at each time step, the evolution of the dynamics and the first-order information of the cost are provided only for the executed control action. We propose an optimization-based control algorithm that iteratively minimizes a data-driven surrogate function for the unknown objective. We prove that the proposed approach incurs sublinear cumulative regret (step-wise suboptimality with respect to an optimal one-step controller) and is worst-case optimal among a broad class of data-driven control algorithms. We also present tractable reformulations of the approach that can leverage off-the-shelf solvers for efficient implementations.

Introduction: The Challenge of On-the-Fly Control

Traditional control strategies often rely on precise mathematical models of system dynamics. However, in real-world scenarios—such as an aircraft experiencing sudden structural damage mid-flight—dynamics can change instantly and unpredictably. In these high-stakes environments, there is no luxury of a pre-training phase or a simulator. The system must be controlled "on-the-fly" using only the data generated during the current trajectory.

This problem is compounded by "bandit feedback": the controller only observes the outcome of the specific action taken, with no information about alternative actions. Bridging the gap between theoretical regret guarantees and practical, real-time implementation is the primary objective of this work.

Methodology: Data-Driven Surrogate Optimization

The proposed approach centers on an iterative optimization process. At each time step $t$, the controller selects an action $u_t$ by minimizing a data-driven surrogate function $m_{t,\alpha,\beta}$. This surrogate is constructed as a weighted combination of a majorant (upper bound) $C_{t-1}^+$ and a minorant (lower bound) $C_{t-1}^-$ of the unknown cost function $C$.

$$m_{t,\alpha,\beta} = \alpha C_{t-1}^+ + \beta C_{t-1}^-$$

The parameters $\alpha$ and $\beta$ are critical as they allow the controller to balance exploration and exploitation. By adjusting these weights, the algorithm can prioritize minimizing the expected cost, reducing uncertainty, or following a lower bound to encourage exploration.

Computational Efficiency and Side Information

A key contribution is showing that for specific choices of $\alpha$ and $\beta$, the optimization problem can be reformulated into a finite number of convex or concave quadratic programs. This allows the use of high-performance solvers like GUROBI, enabling real-time feasibility. Furthermore, the framework can incorporate "side information"—such as known convexity or monotonicity of the cost—to significantly tighten the bounds and accelerate learning.

Theoretical Guarantees and Empirical Results

The authors provide a rigorous proof that the algorithm achieves sublinear cumulative regret. Specifically, the average regret $R_T$ scales at a rate of $O(T^{-2/(n_Z+n_U)})$, where $n_Z$ and $n_U$ represent the dimensions of the state context and control input. This implies that as more data is gathered, the controller's performance converges toward the theoretical optimum. Notably, the algorithm is proven to be worst-case optimal within its class.

Numerical evaluations on unicycle dynamics and a simulated damaged aircraft landing confirm these theoretical findings. In the aircraft scenario, the algorithm successfully regulated altitude and flight path to land safely despite having zero prior knowledge of the damage-altered dynamics.

Conclusion

This work provides a robust framework for controlling unknown nonlinear systems in real-time. By utilizing a flexible surrogate function and leveraging tractable optimization reformulations, the approach achieves both theoretical optimality and practical efficiency. Future research will focus on extending this "one-step" lookahead approach to multi-step model predictive control (MPC) to handle tasks requiring long-term strategic planning.

Summary updated

BibTeX
@article{vinod2023fly,
  author = {Abraham P. Vinod and Arie Israel and Ufuk Topcu},
  title = {{On-the-fly control of unknown nonlinear systems with sublinear regret}},
  journal = {IEEE Trans. Automatic Control},
  year = {2023},
  doi = {10.1109/tac.2022.3186425},
}
Figure