Thompson Sampling for Linear-Quadratic Control Problems

Abstract

We consider the exploration-exploitation tradeoff in linear quadratic (LQ) control problems, where the state dynamics is linear and the cost function is quadratic in states and controls. We analyze the regret of Thompson sampling (TS) (a.k.a. posterior-sampling for reinforcement learning) in the frequentist setting, i.e., when the parameters characterizing the LQ dynamics are fixed. Despite the empirical and theoretical success in a wide range of problems from multi-armed bandit to linear bandit, we show that when studying the frequentist regret TS in control problems, we need to trade-off the frequency of sampling optimistic parameters and the frequency of switches in the control policy. This results in an overall regret of $O(T^{2/3})$, which is significantly worse than the regret $O(\sqrt{T})$ achieved by the optimism-in-face-of-uncertainty algorithm in LQ control problems.

References in corpus (2)

• Deep Exploration via Bootstrapped DQN
• Generalization and Exploration via Randomized Value Functions

Cited by in corpus (15)

• On the Sample Complexity of the Linear Quadratic Regulator
• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Naive Exploration is Optimal for Online LQR
• A Tour of Reinforcement Learning: The View from Continuous Control
• The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint
• Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon
• Regret Minimization in Partially Observable Linear Quadratic Control
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Robust exploration in linear quadratic reinforcement learning
• Episodic Linear Quadratic Regulators with Low-rank Transitions
• Online Learning in Kernelized Markov Decision Processes
• Optimistic robust linear quadratic dual control
• Towards a Dimension-Free Understanding of Adaptive Linear Control
• Exact Asymptotics for Linear Quadratic Adaptive Control
• Alice's Adventures in the Markovian World