Controlling unknown linear dynamics with bounded multiplicative regret

Jacob Carruth, Maximilian F. Eggl, Charles Fefferman, Clarence W. Rowley, Melanie Weber

This paper, titled "Controlling Unknown Linear Dynamics with Bounded Multiplicative Regret," presents a theoretical breakthrough in control theory, specifically addressing how to manage systems with unknown, potentially explosive dynamics over a fixed period of time.

TL;DR

The authors develop a control strategy for linear systems where the internal dynamics are completely unknown and potentially highly unstable. Unlike traditional methods that focus on long-term performance, this strategy guarantees that the total cost remains within a constant factor of the theoretical "perfect-knowledge" optimum, even for a fixed, short time horizon.

What Problem Does This Paper Address?

In classical control theory, the Linear Quadratic Regulator (LQR) is a standard tool for keeping a system (like a drone or a chemical reactor) near a target state while minimizing the "effort" (control cost). However, LQR usually assumes you know the system's parameters.

If the parameters are unknown, you have to learn them "on the fly." Most existing research focuses on additive regret—the difference between your cost and the optimal cost—and looks at what happens as time goes to infinity.

This paper tackles a more stressful scenario:

  1. Fixed Time Horizon ($T$): You don't have forever to learn; you have a strict deadline.
  2. Arbitrary Instability: The unknown parameter $a$ could be very large and positive, meaning the system could explode exponentially if you don't act quickly.
  3. Multiplicative Regret: Instead of looking at the difference in cost, the authors look at the competitive ratio (multiplicative regret). They ask: Can we guarantee our strategy is never more than $C$ times worse than the strategy of someone who knew the parameter from the start?

The authors use the motivating example of a pilot trying to land a severely damaged aircraft—a situation where data is scarce, time is limited, and the cost of failure is catastrophic.

Methods

The authors propose a novel Epoch-based strategy ($\sigma_*$). The core idea is to partition the time interval $[0, T]$ into a "Prologue" and several "Epochs" based on the behavior of the system state $q(t)$.

  • The Prologue/Epoch 0: The controller does nothing ($u=0$) and simply observes how fast the state $q(t)$ grows.
  • Threshold Triggering: The strategy defines thresholds ($1, 2, 4, \dots, 2^\nu$). Every time the state $|q(t)|$ hits a new threshold, a new epoch begins.
  • Learning by Growth: The time it takes to move from one threshold to the next provides a "guess" for the unknown parameter $a$. If the state doubles very quickly, $a$ must be large and positive.
  • The Margin of Safety: When the controller finally intervenes, it doesn't just use the best estimate of $a$. It uses a "margin of safety" (a factor of 4 in their specific formula) to ensure it over-controls rather than under-controls. Under-controlling an unstable system is "dangerous" because the state can grow faster than the controller can react.
  • Mathematical Framework: The problem is modeled using a stochastic differential equation (SDE) driven by Brownian motion. The proof involves complex probabilistic analysis to show that "disasters" (where the estimate is wildly wrong) are exponentially unlikely.

Datasets

Not discussed in the paper. This is a purely theoretical mathematical work. The "evaluation" is done through rigorous proofs rather than empirical testing on specific datasets.

Key Insights and Ideas

  • Multiplicative is Harder: In unstable systems, the optimal cost $S(\sigma_{opt}, a)$ can be very large. A bounded additive regret might be impossible or meaningless, but a bounded multiplicative regret shows the strategy scales correctly with the difficulty of the problem.
  • The Danger of Under-control: The paper highlights that for large positive $a$, the primary risk is under-estimating the instability. If you think the system is stable when it isn't, the state escapes to infinity before you can correct it.
  • Fixed $T$ vs. $T \to \infty$: Most "online learning" algorithms need a long time to converge. This paper proves that you can be "optimally competitive" even in the very first few seconds of operation.
  • "Do Nothing" is sometimes Optimal: For systems that are already very stable (large negative $a$), the best strategy is often to do nothing, as the system's natural dynamics will pull it back to the origin.

Key Results

The main result is Theorem 1, which proves that for any unknown real-valued parameter $a$: $$S(\sigma_*, a) \le C \cdot S(\sigma_{opt}(a), a)$$ Where:

  • $S(\sigma_*, a)$ is the expected cost of their strategy.
  • $S(\sigma_{opt}(a), a)$ is the expected cost of the optimal strategy that knows $a$.
  • $C$ is a constant that depends only on the time horizon $T$, not on the unknown parameter $a$.

This confirms that the strategy is "universally competitive" across the entire real line of possible dynamics.

Limitations and Future Work

  • The Constant $C$: While the authors prove $C$ exists, they don't calculate its smallest possible value. They suggest that a future "strengthened" version of the theorem could find a strategy where $C$ is as small as possible (approaching 1 with a small error $\epsilon$).
  • Toy Problem Constraints: The paper focuses on a 1D "toy problem" (single parameter $a$, single state $q$). Real-world systems are multi-dimensional (matrices instead of scalars).
  • Continuous vs. Discrete: The strategy relies on hitting exact thresholds in continuous time, which might need adaptation for discrete-time computer controllers.

Summary updated

Abstract

We consider a simple control problem in which the underlying dynamics depend on a parameter that is unknown and must be learned. We exhibit a control strategy which is optimal to within a multiplicative constant. While most authors find strategies which are successful as the time horizon tends to infinity, our strategy achieves lowest expected cost up to a constant factor for a fixed time horizon.
BibTeX
@inproceedings{carruth2022controlling,
  author = {Jacob Carruth and Maximilian F. Eggl and Charles Fefferman and Clarence W. Rowley and Melanie Weber},
  title = {{Controlling unknown linear dynamics with bounded multiplicative regret}},
  booktitle = {Revista},
  year = {2022},
  doi = {10.4171/rmi/1377},
}

Loading related content...

Figure