Detailed Instructions: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Problem:<lb>We study the problem of adaptive control of a high dimensional linear quadratic<lb>(LQ) system. Previous work established the asymptotic convergence to an optimal<lb>controller for various adaptive control schemes. More recently, for the average<lb>cost LQ problem, a regret bound of O(<lb><lb>T ) was shown, apart form logarithmic<lb>factors. However, this bound scales exponentially with p, the dimension of the<lb>state space. In this work we consider the case where the matrices describing the<lb>dynamic of the LQ system are sparse and their dimensions are large. We present<lb>an adaptive control scheme that achieves a regret bound of O(p<lb><lb>T ), apart from<lb>logarithmic factors. In particular, our algorithm has an average cost of (1 + o)<lb>times the optimum cost after T = polylog(p)O(1/o). This is in comparison to<lb>previous work on the dense dynamics where the algorithm requires time that scales<lb>exponentially with dimension in order to achieve regret of o times the optimal cost.<lb>We believe that our result has prominent applications in the emerging area of<lb>computational advertising, in particular targeted online advertising and advertising<lb>in social networks.
Solution:
Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systems