Abstract
We consider the problem of controlling an unknown stochastic linear system with quadratic costs - called the adaptive LQ control problem. We re-examine an approach called ''Reward Biased Maximum Likelihood Estimate'' (RBMLE) that was proposed more than forty years ago, and which predates the ''Upper Confidence Bound'' (UCB) method as well as the definition of ''regret'' for bandit problems. It simply added a term favoring parameters with larger rewards to the criterion for parameter estimation. We show how the RBMLE and UCB methods can be reconciled, and thereby propose an Augmented RBMLE-UCB algorithm that combines the penalty of the RBMLE method with the constraints of the UCB method, uniting the two approaches to optimism in the face of uncertainty. We establish that theoretically, this method retains $\Tilde{\mathcal{O}}(\sqrt{T})$ regret, the best-known so far. We further compare the empirical performance of the proposed Augmented RBMLE-UCB and the standard RBMLE (without the augmentation) with UCB, Thompson Sampling, Input Perturbation, Randomized Certainty Equivalence and StabL on many real-world examples including flight control of Boeing 747 and Unmanned Aerial Vehicle. We perform extensive simulation studies showing that the Augmented RBMLE consistently outperforms UCB, Thompson Sampling and StabL by a huge margin, while it is marginally better than Input Perturbation and moderately better than Randomized Certainty Equivalence.
Introduction
Adaptive control of unknown stochastic linear systems with quadratic costs—the adaptive Linear Quadratic (LQ) problem—is a fundamental challenge in control theory and reinforcement learning. The core difficulty lies in the exploration-exploitation dilemma: a controller must balance minimizing immediate costs with gathering enough information about the system's unknown parameters to optimize future performance. Failure to explore effectively can lead to "Certainty Equivalence" traps, where the system stabilizes in a way that prevents the learner from ever discovering the optimal controller.
Historically, two distinct approaches to "optimism in the face of uncertainty" have emerged. The Reward Biased Maximum Likelihood Estimate (RBMLE), proposed over forty years ago, adds a penalty term to the parameter estimation criterion to favor models with lower optimal costs. Conversely, the Upper Confidence Bound (UCB) method, more common in modern bandit literature, searches for the most optimistic parameter within a statistically defined confidence ellipsoid. While UCB offers rigorous theoretical regret bounds, it often exhibits poor empirical performance in complex control tasks. RBMLE, while empirically robust, has lacked tight theoretical guarantees until now.
The Augmented RBMLE-UCB Algorithm
This work introduces the Augmented RBMLE-UCB (ARBMLE) algorithm, which reconciles these two paradigms. ARBMLE treats the RBMLE penalty as a regularizer within the UCB framework. Specifically, the algorithm solves an optimization problem that minimizes a combination of the log-likelihood (data fit) and the optimal cost (reward bias), while explicitly constraining the search to stay within the UCB confidence ellipsoid.
To ensure stability and computational efficiency, ARBMLE employs episodic updates. The system model is recalculated only when the information gathered—quantified by the determinant of the covariance matrix—doubles. A key theoretical contribution is the proof that RBMLE is essentially the Lagrangian version of the UCB optimization problem, allowing the authors to establish a regret bound of $\tilde{\mathcal{O}}(\sqrt{T})$, the best-known order for this class of problems.
Experimental Evaluation
The performance of ARBMLE was evaluated against several state-of-the-art algorithms, including standard UCB (OFULQ), Thompson Sampling (TS), Input Perturbation (IP), Randomized Certainty Equivalence (RCE), and StabL. Testing was conducted across four challenging benchmark environments:
- Unstable Laplacian Dynamics: A system with weakly connected nodes, complicating parameter identification.
- Large Transient Dynamics: Systems characterized by significant state swings before stabilization.
- Unmanned Aerial Vehicle (UAV): A 2D linearized model focusing on position and velocity control.
- Boeing 747 Longitudinal Control: Linearized dynamics of a 747 aircraft at an altitude of 40,000 feet.
Results and Discussion
Empirical results demonstrate that ARBMLE consistently outperforms UCB, Thompson Sampling, and StabL by several orders of magnitude. For instance, in the UAV simulation, the regret of the standard UCB approach (OFULQ) was approximately $10^8$ times higher than that of ARBMLE. As shown in the table below, ARBMLE and its unaugmented counterpart (RBMLE) achieve the lowest regret across nearly all scenarios.
A critical observation is the "Boundary Problem" inherent in standard UCB methods. Algorithms like OFULQ often select parameters at the extreme edge of the confidence interval, leading to aggressive and potentially unstable control actions. In contrast, ARBMLE’s reward bias term typically pulls the estimate into the interior of the confidence ellipsoid, resulting in smoother learning and superior initial regret. Interestingly, simulations showed that ARBMLE and the original unconstrained RBMLE often selected identical parameters, suggesting that the reward bias naturally maintains the estimate within a reasonable range even without explicit constraints.
Conclusion
ARBMLE provides a powerful bridge between classical control theory and modern reinforcement learning, offering both theoretical optimality and practical robustness. While the augmented version is now theoretically grounded, proving the $\tilde{\mathcal{O}}(\sqrt{T})$ bound for the original unconstrained RBMLE remains an open challenge. Future research may also explore efficient global optimization techniques for the non-convex objective function and the extension of this augmented optimism to non-linear systems.
Summary updated