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 theoretical performance of Thompson Sampling (TS) in this setting, specifically focusing on the frequentist regret bound and the fundamental trade-offs between exploration, optimism, and system stability.
Introduction
In Reinforcement Learning (RL), the exploration-exploitation tradeoff is the central challenge: should an agent exploit the current best-known policy or explore the environment to uncover more efficient strategies? In the context of Linear-Quadratic (LQ) control—where system dynamics are linear and costs are quadratic—this tradeoff is particularly nuanced due to the requirement of system stability.
While "Optimism-in-the-Face-of-Uncertainty" (OFU) algorithms have historically dominated the theoretical landscape of LQ control with a regret bound of $\tilde{O}(\sqrt{T})$, Thompson Sampling (TS) has emerged as a popular practical alternative. This paper by Marc Abeille and Alessandro Lazaric (AISTATS 2017) provides a rigorous frequentist analysis of TS in LQ control, revealing a theoretical performance gap that highlights the unique difficulties of randomized exploration in dynamical systems.
The Thompson Sampling Approach to LQR
The authors analyze a version of Thompson Sampling adapted for the Linear-Quadratic Regulator (LQR). The algorithm, referred to as TS-LQR, operates through several key stages:
- Estimation: The unknown system dynamics parameters ($A_*$ and $B_*$) are estimated using Regularized Least Squares (RLS) based on observed transitions.
- Randomization: Instead of selecting the most optimistic parameters within a confidence set (as OFU does), TS samples a "perturbed" parameter $\tilde{\theta}_t$ from a distribution centered at the RLS estimate.
- Lazy Updates: To maintain control stability, the policy is not updated at every timestep. Instead, updates occur only when the collected information doubles or a maximum episode length is reached.
- Rejection Sampling: The algorithm ensures that any sampled model is "admissible" (stabilizable) before it is used to derive a control policy.
The $T^{2/3}$ Hurdle: Why TS Lags Behind OFU
The core finding of the paper is that in a frequentist setting—where there is one fixed "true" parameter and no helpful prior—TS achieves a regret of $\tilde{O}(T^{2/3})$. This is significantly slower than the $\tilde{O}(\sqrt{T})$ achieved by optimistic algorithms. This gap arises from a fundamental conflict between two requirements:
1. The Need for Optimism
To minimize regret, an algorithm must occasionally select a model that is more optimistic (lower cost) than the true model. In TS, optimism is stochastic. The agent only samples an optimistic model with a certain constant probability $p$. To ensure enough optimistic samples are drawn to drive learning, the agent needs to sample relatively frequently.
2. The Switching Penalty and Stability
Unlike simple multi-armed bandit problems, control systems incur a "consistency regret" or switching penalty. Every time the control policy changes, the system must settle into the new dynamics. Frequent switching can lead to instability and high regret.
3. The Frequentist Bottleneck
In a Bayesian setting, a well-chosen prior can assist exploration. However, in the frequentist analysis, the agent might be stuck with a "pessimistic" estimate for an extended period. To overcome this and find an optimistic sample, the agent must sample often; yet, to keep the system stable, it must switch rarely. Balancing these opposing forces—sampling frequently enough to encounter optimism versus switching infrequently enough to maintain stability—mathematically results in the $\tilde{O}(T^{2/3})$ regret bound.
Key Results and Limitations
- Regret Analysis: The paper proves the $\tilde{O}(T^{2/3})$ bound specifically for the one-dimensional case (scalar states and actions).
- Probability of Optimism: A major theoretical contribution is Lemma 3, which proves that even in a frequentist setting, TS maintains a constant, non-zero probability of sampling an optimistic parameter, providing the necessary foundation for the regret analysis.
- Dimensionality: While the framework is general, the specific $T^{2/3}$ bound and the optimism lemma are formally proven for $n=1, d=1$. Extending this to higher dimensions remains a point of ongoing research.
Conclusion
This research clarifies the theoretical cost of using Thompson Sampling in control problems. While TS is often easier to implement and performs well in empirical tests, the $T^{2/3}$ bound reveals an intrinsic "penalty" for randomized exploration in the face of dynamical stability requirements. Reconciling this theoretical pessimism with the practical success of Thompson Sampling remains a significant open question in the field of adaptive control.
Summary updated