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.
Introduction
In Reinforcement Learning (RL), the "exploration-exploitation" tradeoff is a fundamental challenge. Linear-Quadratic (LQ) control represents a classic setting within this domain, where state dynamics are linear and costs are quadratic. This model is widely applicable to physical systems, such as maintaining the stability of a drone or managing industrial processes.
When the underlying physics (the system parameters) are known, the optimal control policy can be found by solving the Riccati equation. However, when these parameters are unknown, the agent must learn them through interaction while simultaneously trying to minimize costs. Two primary paradigms exist for this: Optimism-in-the-Face-of-Uncertainty (OFU), which acts according to the most favorable model consistent with the data, and Thompson Sampling (TS), which samples a model from a posterior distribution and acts optimally for that sample.
While TS is celebrated for its simplicity and efficiency in multi-armed and linear bandit problems, its performance in control problems—where current actions dictate future states—has remained less understood in the frequentist setting.
Methodology
This research provides the first frequentist regret analysis of TS for LQ control. The learner employs a specific algorithmic framework to balance learning and performance:
- Parameter Estimation: The learner uses Regularized Least Squares (RLS) to estimate the system dynamics based on observed transitions.
- Randomized Sampling: Instead of using the estimate directly, the learner samples a "perturbed" parameter from a Gaussian distribution centered at the estimate. The variance of this distribution reflects the current level of uncertainty.
- Lazy Updates: To maintain system stability, the policy is not updated at every time step. Instead, updates occur only when the collected data has significantly improved (governed by a "determinant doubling" rule) or when a maximum episode length ($\tau$) is reached.
To analyze this, the authors utilize a novel proof strategy involving a weighted Poincaré inequality. This mathematical tool allows for a direct link between "optimality regret" (the cost of not selecting the true best model) and "consistency regret" (the cost associated with policy switches and state prediction errors).
The Stability-Optimism Conflict
The core finding of this work is a fundamental conflict in control problems that does not exist in simpler bandit settings: the trade-off between sampling for optimism and policy stability.
In bandit problems, one can sample a new model at every step without penalty. However, in LQ control, changing the control policy too frequently creates instability, leading to high consistency regret. Conversely, if the learner does not sample frequently enough, they may fail to pick an "optimistic" model that encourages necessary exploration.
Because TS relies on random sampling to achieve optimism—rather than explicitly forcing it like OFU—it requires more frequent sampling to ensure sufficient exploration. This increased switching frequency degrades the stability of the control system, resulting in a frequentist regret bound of $\tilde{O}(T^{2/3})$.
Key Results and Comparison
The analysis demonstrates a significant theoretical gap between TS and OFU in the frequentist setting:
- Regret Bound: The paper proves a frequentist regret bound of $\tilde{O}(T^{2/3})$ for one-dimensional LQ systems.
- Performance Gap: This is notably worse than the $O(\sqrt{T})$ regret achieved by the OFU-LQ algorithm.
- Frequentist vs. Bayesian: While previous research showed that TS can achieve $O(\sqrt{T})$ in a Bayesian setting (where parameters are assumed to be drawn from a known prior), this paper highlights that without a helpful prior, the problem becomes significantly more difficult for randomized sampling methods.
Limitations and Future Directions
While this work provides a rigorous foundation for understanding TS in control, several avenues for future research remain:
- Dimensionality: The current detailed analysis of the probability of optimism is focused on one-dimensional systems (scalar states and controls). Extending these proofs to higher-dimensional systems is a natural next step.
- Tightness of the Bound: It is currently an open question whether the $O(T^{2/3})$ rate is an inherent limitation of the Thompson Sampling approach in control, or if a more refined analysis or algorithmic variation could recover the $O(\sqrt{T})$ rate.
- Alternative Randomization: The results suggest an intrinsic limitation to parameter sampling. Future work might explore whether other forms of randomization, such as perturbed history or Langevin dynamics, could offer better stability-exploration trade-offs.
Summary updated