On the Regret of Recursive Methods for Discrete-Time Adaptive Control with Matched Uncertainty

Aren Karapetyan, Efe C. Balta, Anastasios Tsiamis, Andrea Iannelli, John Lygeros

Introduction

In the field of adaptive control, a fundamental tension exists between the need to control a system and the need to learn its unknown dynamics. This "cost of learning" is formally quantified as regret—the cumulative difference in performance between an adaptive controller and an ideal controller that possesses full knowledge of the system parameters from the start. While continuous-time adaptive control theory is well-established, discrete-time systems—which are the standard for digital implementation—present unique challenges that have historically made finite regret guarantees difficult to achieve without unrealistic assumptions.

Researchers from ETH Zürich and the University of Stuttgart have recently addressed this gap, proposing a novel Recursive Proximal Learning (RPL) algorithm. Their work demonstrates that it is possible to achieve finite regret in discrete-time adaptive control using a fully causal, implementable framework.

The Challenge of Causality in Discrete Time

The primary hurdle in discrete-time adaptive control is the inherent one-step delay: a control input is applied at time $t$, but its effect on the system state (and the resulting error) is not observed until time $t+1$. In the context of learning, this creates a causality dilemma. Many existing proofs for finite regret in discrete-time systems rely on non-causal updates, effectively assuming the controller knows the future error before it occurs. Such methods are mathematically convenient but impossible to deploy in real-world digital controllers.

Furthermore, while many adaptive controllers are "asymptotically stable"—meaning they eventually succeed in tracking a reference—they do not necessarily bound the total error accumulated during the learning phase. Without a finite regret guarantee, the system might incur an arbitrarily large cost before the parameters are sufficiently identified.

Recursive Proximal Learning (RPL)

To solve the causality and regret issues, the authors introduce the Recursive Proximal Learning (RPL) algorithm. Unlike standard gradient descent or simple recursive updates, RPL is based on the proximal point method from optimization. At each time step, the algorithm solves a localized optimization problem to update its parameter estimates.

Stability via E-$\delta$-ISS

The theoretical foundation of this approach is Incremental Input-to-State Stability (E-$\delta$-ISS). The authors demonstrate that if the nominal (known) part of the system is stable, and the parameter estimation process is contractive, the overall closed-loop system will converge to the desired trajectory. RPL ensures that once enough data has been collected, the parameter estimates become strictly contractive relative to the true values.

Key Insights: Excitation and Regret

A critical contribution of this research is the refinement of "excitation" requirements. To learn the dynamics of a system, the system must be "excited"—essentially moved in a way that reveals its underlying parameters.

  1. Sufficient Excitation (SE) vs. Persistence of Excitation (PE): Traditional methods like Recursive Least Squares with Exponential Forgetting (RLSFF) typically require Persistence of Excitation, meaning the system must be continually "shaken" forever to maintain accurate estimates. In contrast, RPL achieves finite regret under the weaker condition of Sufficient Excitation. Once the system has been excited enough to identify the parameters, the learning cost effectively stops accumulating.
  2. Finite Regret is Causal: The authors rigorously prove that RPL achieves $O(1)$ (finite) regret without requiring non-causal information. This confirms that the "cost of learning" in discrete-time systems can be strictly bounded in practical, real-world implementations.
  3. Regret Scaling: The analysis shows that regret scales primarily with the time $T_s$ required to satisfy the excitation condition. Once the parameters are identified, the adaptive controller's performance matches that of the ideal controller.

Numerical Evaluation

The researchers validated their findings using a Discrete-Time Model Reference Adaptive Control (MRAC) simulation. The plant was tasked with mimicking a specific reference model, a standard benchmark in control theory. The simulation compared RPL against two benchmarks:

  • RLSFF: A classic recursive estimation technique.
  • Standard MRAC: A command-governor-based adaptive controller.

Results indicated that the RPL-based controller significantly outperformed both benchmarks, demonstrating superior tracking precision and faster convergence of parameter estimates. Crucially, the RPL estimates remained stable even when the system was not being persistently excited, whereas RLSFF performance can degrade if excitation ceases.

Limitations and Future Directions

While the paper marks a significant step forward, several constraints remain for future exploration:

  • Matched Uncertainty: The current framework assumes that unknown dynamics act on the system through the same channels as the control input. Handling "unmatched" uncertainty is a more complex problem.
  • Basis Functions: The method assumes the structure of the uncertainty (the basis matrices) is known, even if the weights are not.
  • Stochastic Noise: The current study focuses on a deterministic setting. Extending these finite regret proofs to systems with stochastic noise is a primary goal for future research.
  • Goal-Oriented Control: The authors suggest moving from optimizing for "estimation error" to "goal-oriented" control, where the algorithm directly optimizes the final control objective, such as energy efficiency or safety margins.

Conclusion

By bridging the gap between optimization theory and discrete-time control, the RPL algorithm provides a robust framework for adaptive systems. It proves that finite regret is not just a theoretical ideal but a reachable goal for causal, digital controllers, ensuring that the "cost of learning" remains bounded even in uncertain environments.

Summary updated

BibTeX
@inproceedings{karapetyan2024regret,
  author = {Aren Karapetyan and Efe C. Balta and Anastasios Tsiamis and Andrea Iannelli and John Lygeros},
  title = {{On the Regret of Recursive Methods for Discrete-Time Adaptive Control with Matched Uncertainty}},
  booktitle = {CDC},
  year = {2024},
  url = {https://openreview.net/forum?id=wkG7VE4nQH},
}
Figure