Related papers: Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems

Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems

URL: http://arxiv.org/abs/2201.01680v4
Date: Wed, 12 Jun 2024 13:11:28 GMT
Title: Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems
Authors: Ingvar Ziemann, Henrik Sandberg,
Abstract summary: We derive regret lower bounds exhibiting scaling on the order of magnitude $sqrtT$ in the time horizon $T$. Our bounds accurately capture the role of control-theoretic parameters and we are able to show that systems that are hard to control are also hard to learn to control.
Score: 6.261682379939611
License: http://creativecommons.org/licenses/by/4.0/
Abstract: TWe establish regret lower bounds for adaptively controlling an unknown linear Gaussian system with quadratic costs. We combine ideas from experiment design, estimation theory and a perturbation bound of certain information matrices to derive regret lower bounds exhibiting scaling on the order of magnitude $\sqrt{T}$ in the time horizon $T$. Our bounds accurately capture the role of control-theoretic parameters and we are able to show that systems that are hard to control are also hard to learn to control; when instantiated to state feedback systems we recover the dimensional dependency of earlier work but with improved scaling with system-theoretic constants such as system costs and Gramians. Furthermore, we extend our results to a class of partially observed systems and demonstrate that systems with poor observability structure also are hard to learn to control.

Related papers

Learning Decentralized Linear Quadratic Regulators with $\sqrt{T}$ Regret [1.529943343419486]
We propose an online learning algorithm that adaptively designs a decentralized linear quadratic regulator when the system model is unknown a priori. We show that our controller enjoys an expected regret that scales as $sqrtT$ with the time horizon $T$ for the case of partially nested information pattern.
arXiv Detail & Related papers (2022-10-17T09:29:01Z)
Learning-Based Adaptive Control for Stochastic Linear Systems with Input Constraints [3.8004168340068336]
We propose a certainty-equivalence scheme for adaptive control of scalar linear systems subject to additive, i.i.d. Assuming that the system is at-worst marginally stable, mean square boundedness of the closed-loop system states is proven.
arXiv Detail & Related papers (2022-09-15T04:49:06Z)
Learning to Control Linear Systems can be Hard [19.034920102339573]
We study the statistical difficulty of learning to control linear systems. We prove that learning complexity can be at most exponential with the controllability index, that is the degree of underactuation.
arXiv Detail & Related papers (2022-05-27T15:07:30Z)
Deep Learning Approximation of Diffeomorphisms via Linear-Control Systems [91.3755431537592]
We consider a control system of the form $dot x = sum_i=1lF_i(x)u_i$, with linear dependence in the controls. We use the corresponding flow to approximate the action of a diffeomorphism on a compact ensemble of points.
arXiv Detail & Related papers (2021-10-24T08:57:46Z)
Sparsity in Partially Controllable Linear Systems [56.142264865866636]
We study partially controllable linear dynamical systems specified by an underlying sparsity pattern. Our results characterize those state variables which are irrelevant for optimal control.
arXiv Detail & Related papers (2021-10-12T16:41:47Z)
Finite-time System Identification and Adaptive Control in Autoregressive Exogenous Systems [79.67879934935661]
We study the problem of system identification and adaptive control of unknown ARX systems. We provide finite-time learning guarantees for the ARX systems under both open-loop and closed-loop data collection.
arXiv Detail & Related papers (2021-08-26T18:00:00Z)
Adaptive Control and Regret Minimization in Linear Quadratic Gaussian (LQG) Setting [91.43582419264763]
We propose LqgOpt, a novel reinforcement learning algorithm based on the principle of optimism in the face of uncertainty. LqgOpt efficiently explores the system dynamics, estimates the model parameters up to their confidence interval, and deploys the controller of the most optimistic model.
arXiv Detail & Related papers (2020-03-12T19:56:38Z)
Regret Minimization in Partially Observable Linear Quadratic Control [91.43582419264763]
We study the problem of regret in partially observable linear quadratic control systems when the model dynamics are unknown a priori. We propose a novel way to decompose the regret and provide an end-to-end sublinear regret upper bound for partially observable linear quadratic control.
arXiv Detail & Related papers (2020-01-31T22:35:08Z)
Improper Learning for Non-Stochastic Control [78.65807250350755]
We consider the problem of controlling a possibly unknown linear dynamical system with adversarial perturbations, adversarially chosen convex loss functions, and partially observed states. Applying online descent to this parametrization yields a new controller which attains sublinear regret vs. a large class of closed-loop policies. Our bounds are the first in the non-stochastic control setting that compete with emphall stabilizing linear dynamical controllers.
arXiv Detail & Related papers (2020-01-25T02:12:48Z)

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