Online Tracking with Predictions for Nonlinear Systems with Koopman Linear Embedding

This paper proposes a model-free predictive tracking algorithm for unknown nonlinear systems with Koopman linear embeddings that leverages Willems' fundamental lemma to achieve dynamic regret decaying exponentially with the prediction horizon, effectively bridging the performance gap between nonlinear and lifted linear counterparts.

The Gist

Imagine you are driving a car on a winding, foggy road. You don't have a map of the entire route (the system dynamics are unknown), and you can't see the road more than a few seconds ahead (you only have short-term predictions). Your goal is to stay perfectly on a moving target line that keeps changing direction.

This is the problem the paper solves: How do you control a complex, unpredictable machine when you don't know the rules of physics, but you have a little bit of future information?

Here is the breakdown of their solution using simple analogies.

1. The Problem: The "Black Box" Car

Most robots and autonomous systems are nonlinear. This means they don't move in straight lines or simple curves. If you turn the steering wheel a little, the car might turn a little. But if you turn it hard, the physics change, and the car might slide or spin in a completely different way.

Usually, to control these, you need a perfect mathematical model of the car. But in the real world, we often don't have that model. We just have a "black box."

2. The Magic Trick: The "Koopman Lifting" (The 3D Glasses)

The authors use a mathematical concept called Koopman Lifting.

• The Analogy: Imagine you are looking at a shadow puppet show on a wall. The shadow (the real system) moves in weird, complex, non-linear ways. It's hard to predict.
• The Trick: The authors put on a pair of "3D glasses" (the Lifting Function). Suddenly, you aren't looking at the shadow anymore; you are looking at the actual puppet in 3D space.
• The Result: In this new 3D space, the puppet's movements are perfectly linear (straight and predictable). Even though the shadow on the wall looks chaotic, the puppet in the 3D world moves in a simple, straight line.

The paper proves that if you can find this "3D space" (which they assume exists for this class of systems), you can solve the hard problem by solving an easy, linear problem in that new space.

3. The Solution: The "Data-Driven GPS" (No Map Needed)

Usually, to use this 3D trick, you need to know exactly what the "glasses" look like (the mathematical formula). But the authors say: "We don't need to know the formula!"

They use a method based on Willems' Fundamental Lemma.

• The Analogy: Imagine you want to drive a car, but you don't know the engine's specs. However, you have a video recording of someone else driving that exact car for a long time.
• The Method: Instead of trying to write down the engine's physics equations, the computer looks at the video. It says, "Okay, in the video, when the car was in this position and the driver did this action, the car went there."
• The Magic: By stitching together thousands of tiny snippets from that video, the computer can predict exactly what will happen next, even without knowing the engine's internal math. It builds a "model" purely from past data.

4. The Strategy: The "Receding Horizon" (The Flashlight)

The algorithm works like a flashlight in the dark.

• You can only see W steps ahead (the prediction horizon).
• You calculate the best path for those W steps.
• You take one step.
• Then, you move the flashlight forward, see the next W steps, and recalculate.

The paper shows that if your flashlight (prediction horizon) is long enough, you can navigate the fog perfectly, even if you don't know the road rules.

5. The Big Result: "Regret" Drops Like a Stone

In control theory, "Regret" is a score of how much worse you did compared to a perfect, all-knowing god who knew the whole future.

• The Finding: The authors proved that as you increase the length of your "flashlight" (the prediction horizon), your mistakes (regret) don't just go down slowly; they vanish exponentially.
• The Metaphor: If you double the distance you can see ahead, your mistakes don't just get cut in half; they get cut by a factor of ten, then a hundred, then a thousand.
• Why it matters: This means you don't need a super-computer or a perfect model. You just need a slightly longer look into the future, and the system becomes incredibly accurate.

Summary

The paper is about teaching a robot to drive a wild, unpredictable car by:

1. Changing the perspective (Koopman Lifting) to make the chaos look like a straight line.
2. Using past video footage (Data-Driven) instead of a physics textbook to learn how the car moves.
3. Looking a little further ahead (Prediction Horizon) to ensure stability.

They proved mathematically that this works, and their experiments showed that the more you can "see" into the future, the closer the robot gets to the perfect path, even if the system is a complete mystery.

Technical Summary

Here is a detailed technical summary of the paper "Online Tracking with Predictions for Nonlinear Systems with Koopman Linear Embedding."

1. Problem Statement

The paper addresses the online tracking problem for unknown nonlinear dynamical systems where the agent must follow a time-varying target trajectory.

• Setting: The system dynamics $z_{t+1} = f(z_t, u_t)$ are unknown. The agent operates in a non-stationary environment where only short-horizon predictions of future target states ($r_{t:t+W-1}$) are available at each time step $t$.
• Goal: Minimize the cumulative tracking error and control effort over a finite horizon $T$.
• Performance Metric: The authors use Dynamic Regret, which compares the cumulative cost of the online policy against the optimal non-causal policy (the best possible control sequence if the entire future trajectory and system dynamics were known in hindsight).
• Challenge: Extending dynamic regret guarantees from linear systems to nonlinear, model-free settings is difficult due to the complexity of nonlinear dynamics and the lack of explicit models.

2. Methodology

The proposed approach leverages Koopman Operator Theory to transform the nonlinear problem into a linear one, combined with Data-Driven Predictive Control (DDPC) based on Willems' Fundamental Lemma.

A. Koopman Linear Embedding

The authors assume the nonlinear system is Koopman-linearizable. This means there exists a lifting function $\psi: \mathbb{R}^{n_z} \to \mathbb{R}^{n_x}$ such that the lifted state $x_t = \psi(z_t)$ evolves linearly:
$$x_{t+1} = A x_t + B u_t$$
and the original state is recovered via $z_t = C x_t$.

• Key Insight: Even though the exact matrices $(A, B, C)$ and function $\psi$ are unknown, the paper establishes that the cumulative cost and dynamic regret of the nonlinear tracking problem are mathematically equivalent to those of the lifted linear problem.

B. Unified Predictive Tracking Algorithm (Algorithm 1)

The paper proposes a Model Predictive Control (MPC) framework that unifies three variants, all producing identical control actions under the Koopman assumption:

1. Nonlinear MPC (N-MPC): Optimizes directly over unknown nonlinear dynamics (theoretical benchmark).
2. Lifted Linear MPC (L-MPC): Optimizes over the known linear Koopman dynamics.
3. Data-Driven MPC (DDPC): The core practical contribution. It uses offline trajectory data to enforce dynamics constraints without explicit system identification.
   • It constructs a data matrix $H_d$ from offline input-state trajectories.
   • It solves a quadratic program (QP) at each step to find control inputs that satisfy the linear constraints implied by the data (via the extended Willems' Fundamental Lemma).
   • Advantage: It bypasses the need to identify $f$, $\psi$, or the matrices $A, B, C$.

C. Control Policy Structure

The optimal policy for the lifted linear problem is characterized by a closed-form expression involving:

• Feedback Gain: Stabilizes the tracking error.
• Feedforward Gain: Compensates for the time-varying reference trajectory.
  The online MPC policy approximates this optimal policy using a receding horizon $W$.

3. Key Contributions

1. Equivalence of Regret: The paper proves that for Koopman-linearizable systems, the dynamic regret of the nonlinear tracking problem is identical to the dynamic regret of its lifted linear counterpart. This allows the application of linear control theory to nonlinear problems.
2. First Dynamic Regret Bound for Nonlinear Systems: The authors establish the first theoretical dynamic regret bound for online tracking in unknown Koopman-linearizable nonlinear systems.
   • Theorem 5.1: The dynamic regret scales as $O(W^2 \lambda_\infty^{2W} T)$, where $T$ is the full horizon and $W$ is the prediction horizon.
   • Implication: The regret grows linearly with $T$ but decays exponentially with the prediction horizon $W$. A prediction horizon of $W = \Theta(\log T)$ is sufficient to achieve constant $O(1)$ regret.
3. Model-Free Stability without Terminal Costs: Unlike standard MPC which often requires carefully designed terminal costs to ensure stability, this method ensures state boundedness (stability) solely through a sufficiently long prediction horizon.
4. Relaxed Assumptions: The analysis holds under positive semidefinite stage costs and detectability, rather than requiring the stricter positive definite cost assumption often found in linear regret analyses. This is crucial because the Koopman lifting matrix $C$ often results in a singular (non-full rank) cost matrix in the lifted space.

4. Results

Theoretical Results

• Regret Decay: The dynamic regret bound demonstrates that increasing the prediction horizon $W$ exponentially reduces the performance gap between the online controller and the optimal offline controller.
• Stability: The lifted MPC state trajectory remains uniformly bounded provided $W$ exceeds a stabilizing window $\Delta_{stab}$, which depends on the spectral radius of the closed-loop system.

Numerical Experiments

• Koopman-Linearizable System: Experiments on a nonlinear system (similar to Example 2.1) validated the theoretical bounds.
  • Tracking error decreased as $W$ increased.
  • Dynamic regret decayed exponentially with $W$, matching the theoretical prediction.
  • The decay rate was influenced by the control cost matrix $R$ and reference magnitude $M$.
• Non-Koopman System (Extension): The authors applied a regularized version of the DDPC (Reg-DDPC) to a two-wheeled robot (a system not strictly Koopman-linearizable).
  • By using $L_1$ regularization and switching data libraries based on the robot's orientation, the method achieved effective tracking of a complex heart-shaped trajectory.
  • Longer prediction horizons improved recovery from sharp turns and reduced drift.

5. Significance

This work bridges a critical gap between data-driven control and nonlinear system theory.

• Theoretical Breakthrough: It provides the first rigorous dynamic regret guarantees for online control of unknown nonlinear systems using only short-term predictions and offline data.
• Practical Utility: The proposed Data-Driven Predictive Control (DDPC) algorithm requires no explicit model identification or knowledge of the Koopman lifting function. It relies purely on historical data, making it highly applicable to real-world scenarios where system models are unavailable or too complex to derive.
• Robustness: The method demonstrates that stability and performance in nonlinear tracking can be achieved through prediction horizon length rather than complex terminal cost design, simplifying controller implementation.

In summary, the paper demonstrates that by exploiting the Koopman structure, one can treat complex nonlinear tracking problems as linear ones, enabling the use of powerful data-driven predictive control techniques with strong theoretical performance guarantees.