Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently
This work addresses the challenge of efficient learning in control systems for applications like robotics and autonomous systems, providing significant improvements in regret bounds compared to prior results.
The paper tackles the problem of learning in Linear Quadratic Control systems with unknown transition parameters, achieving regret that scales only logarithmically with the number of steps in specific scenarios, such as when only the state transition matrix A is unknown or when only B is unknown under a non-degeneracy condition, while showing that square root regret is unavoidable when this condition is violated.
We consider the problem of learning in Linear Quadratic Control systems whose transition parameters are initially unknown. Recent results in this setting have demonstrated efficient learning algorithms with regret growing with the square root of the number of decision steps. We present new efficient algorithms that achieve, perhaps surprisingly, regret that scales only (poly)logarithmically with the number of steps in two scenarios: when only the state transition matrix $A$ is unknown, and when only the state-action transition matrix $B$ is unknown and the optimal policy satisfies a certain non-degeneracy condition. On the other hand, we give a lower bound that shows that when the latter condition is violated, square root regret is unavoidable.