Regret Analysis: a control perspective

• URL: http://arxiv.org/abs/2501.04572v3
• Date: Thu, 23 Jan 2025 14:33:33 GMT
• Title: Regret Analysis: a control perspective
• Authors: Travis E. Gibson, Sawal Acharya,
• Abstract summary: In adaptive control there are usually two objectives: 1) prove that all time varying parameters/states of the system are bounded, and 2) that the instantaneous error between the adaptively controlled system and a reference system converges to zero over time (or at least a compact set) For online learning the performance of algorithms is often characterized by the regret the algorithm incurs. In this work we discuss these differences in detail through the regret based analysis of gradient descent for convex functions and the control based analysis of a streaming regression problem.
• Score: 0.4604003661048266
• License:
• Abstract: Online learning and model reference adaptive control have many interesting intersections. One area where they differ however is in how the algorithms are analyzed and what objective or metric is used to discriminate "good" algorithms from "bad" algorithms. In adaptive control there are usually two objectives: 1) prove that all time varying parameters/states of the system are bounded, and 2) that the instantaneous error between the adaptively controlled system and a reference system converges to zero over time (or at least a compact set). For online learning the performance of algorithms is often characterized by the regret the algorithm incurs. Regret is defined as the cumulative loss (cost) over time from the online algorithm minus the cumulative loss (cost) of the single optimal fixed parameter choice in hindsight. Another significant difference between the two areas of research is with regard to the assumptions made in order to obtain said results. Adaptive control makes assumptions about the input-output properties of the control problem and derives solutions for a fixed error model or optimization task. In the online learning literature results are derived for classes of loss functions (i.e. convex) while a priori assuming certain signals are bounded. In this work we discuss these differences in detail through the regret based analysis of gradient descent for convex functions and the control based analysis of a streaming regression problem. We close with a discussion about the newly defined paradigm of online adaptive control.

Related papers

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Stochastic Optimal Control Matching [53.156277491861985]
  Our work introduces Optimal Control Matching (SOCM), a novel Iterative Diffusion Optimization (IDO) technique for optimal control. The control is learned via a least squares problem by trying to fit a matching vector field. Experimentally, our algorithm achieves lower error than all the existing IDO techniques for optimal control.
  arXiv  Detail & Related papers  (2023-12-04T16:49:43Z)
• Data-Driven H-infinity Control with a Real-Time and Efficient Reinforcement Learning Algorithm: An Application to Autonomous Mobility-on-Demand Systems [3.5897534810405403]
  This paper presents a model-free, real-time, data-efficient Q-learning-based algorithm to solve the H$_infty$ control of linear discrete-time systems. An adaptive optimal controller is designed and the parameters of the action and critic networks are learned online without the knowledge of the system dynamics.
  arXiv  Detail & Related papers  (2023-09-16T05:02:41Z)
• Solving Elliptic Optimal Control Problems via Neural Networks and Optimality System [3.8704302640118864]
  We investigate a neural network based solver for optimal control problems (without / with box constraint) It employs deep neural networks to represent the solutions to the reduced system. We present several numerical examples to illustrate the method and compare it with two existing ones.
  arXiv  Detail & Related papers  (2023-08-23T05:18:19Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• Online estimation and control with optimal pathlength regret [52.28457815067461]
  A natural goal when designing online learning algorithms is to bound the regret of the algorithm in terms of the temporal variation of the input sequence. Data-dependent "pathlength" regret bounds have recently been obtained for a wide variety of online learning problems, including OCO and bandits.
  arXiv  Detail & Related papers  (2021-10-24T22:43:15Z)
• Strongly Adaptive OCO with Memory [49.319621885036035]
  We propose the first strongly adaptive algorithm for online learning with memory. Our algorithm results in a strongly adaptive regret bound for the control of linear time-varying systems.
  arXiv  Detail & Related papers  (2021-02-02T17:26:08Z)
• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems [91.43582419264763]
  We study the problem of system identification and adaptive control in partially observable linear dynamical systems. We present the first model estimation method with finite-time guarantees in both open and closed-loop system identification. We show that AdaptOn is the first algorithm that achieves $textpolylogleft(Tright)$ regret in adaptive control of unknown partially observable linear dynamical systems.
  arXiv  Detail & Related papers  (2020-03-25T06:00:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.