# Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systems

arXiv: https://arxiv.org/abs/1303.5984 · HTML: https://mlsanity.com/paper/1303.5984/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Mar 2013.

## Built on by (most cited first, 13 of 13)

- [Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient](https://mlsanity.com/paper/2011.04019/) (2020)
- [Optimal Rates for Bandit Nonstochastic Control](https://mlsanity.com/paper/2305.15352/) (2023)
- [Efficient Diversity-based Experience Replay for Deep Reinforcement Learning](https://mlsanity.com/paper/2410.20487/) (2024)
- [Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems](https://mlsanity.com/paper/2105.07310/) (2021)
- [Augmented RBMLE-UCB Approach for Adaptive Control of Linear Quadratic Systems](https://mlsanity.com/paper/2201.10542/) (2022)
- [Rate-Optimal Online Convex Optimization in Adaptive Linear Control](https://mlsanity.com/paper/2206.01426/) (2022)
- [Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics](https://mlsanity.com/paper/2203.01170/) (2022)
- [Actor-Critic based Improper Reinforcement Learning](https://mlsanity.com/paper/2207.09090/) (2022)
- [Does Sparsity Help in Learning Misspecified Linear Bandits?](https://mlsanity.com/paper/2303.16998/) (2023)
- [Learning to Stabilize Unknown LTI Systems on a Single Trajectory under Stochastic Noise](https://mlsanity.com/paper/2406.00234/) (2024)
- [Regret Analysis of Distributed Online Control for LTI Systems with Adversarial Disturbances](https://mlsanity.com/paper/2310.03206/) (2023)
- [Improper Reinforcement Learning with Gradient-based Policy Optimization](https://mlsanity.com/paper/2102.08201/) (2021)
- [Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamics](https://mlsanity.com/paper/2202.05799/) (2022)

## Abstract (arXiv)

We study the problem of adaptive control of a high dimensional linear quadratic (LQ) system. Previous work established the asymptotic convergence to an optimal controller for various adaptive control schemes. More recently, for the average cost LQ problem, a regret bound of O(√T) was shown, apart form logarithmic factors. However, this bound scales exponentially with p, the dimension of the state space. In this work we consider the case where the matrices describing the dynamic of the LQ system are sparse and their dimensions are large. We present an adaptive control scheme that achieves a regret bound of O(p √T), apart from logarithmic factors. In particular, our algorithm has an average cost of (1+eps) times the optimum cost after T = polylog(p) O(1/eps2). This is in comparison to previous work on the dense dynamics where the algorithm requires time that scales exponentially with dimension in order to achieve regret of eps times the optimal cost. We believe that our result has prominent applications in the emerging area of computational advertising, in particular targeted online advertising and advertising in social networks.