Randomized Certainty Equivalence for Adaptive Linear Control

22 concepts22 papers1 proposal

When designing an autonomous system—whether it is a quadcopter navigating wind gusts or a power grid balancing supply and demand—we face a fundamental tension between two fields of thought. As noted by Boffi et al. in Regret Bounds for Adaptive Nonlinear Control, classical adaptive control focuses on asymptotic stability (ensuring the system eventually behaves), while reinforcement learning (RL) focuses on regret (minimizing the performance lost while learning).

The gold standard for evaluating modern adaptive controllers is the Linear Quadratic Regulator (LQR) with unknown dynamics. Here, the system transitions according to:

$$x_{t+1} = Ax_t + Bu_t + w_t$$

where $x_t$ is the state, $u_t$ is the control input, and $w_t$ is random environmental noise. The matrices $A$ and $B$ are completely unknown. Our goal is to minimize a quadratic cost function over time, matching the performance of an optimal controller that knows $A$ and $B$ from the start.

To achieve this, a powerful and intuitive framework has emerged: Randomized Certainty Equivalence with Lazy Updates. This approach decouples system identification from control, injecting structured noise to ensure thorough exploration, and updating the controller on a calculated, "lazy" schedule to maintain physical stability.


The Certainty Equivalence Principle

The simplest way to control an unknown system is to separate learning from acting. This is known as nominal control or the Certainty Equivalence (CE) principle. As Recht explains in A Tour of Reinforcement Learning: The View from Continuous Control, this strategy proceeds in two clean steps:

  1. System Identification: Use standard regression (like regularized least squares) on past states and actions to construct estimates of the dynamics, $\hat{A}$ and $\hat{B}$.
  2. Control Synthesis: Treat these estimates as the absolute ground truth ("certainty") and solve the standard control equations—such as the Discrete Algebraic Riccati Equation—to derive the optimal control law $u_t = K(\hat{A}, \hat{B})x_t$.

This mechanism allows the controller to exploit the known physics and structural properties of the system rather than relying on blind trial-and-error.

The Certainty Equivalence Trap

Despite its elegance, pure certainty equivalence suffers from a catastrophic failure mode: self-reinforcing suboptimality.

If your initial parameter estimates are slightly wrong, the resulting controller might steer the system into a narrow subspace of the state space. Because the controller is purely greedy, it keeps taking actions within this subspace, never gathering the data required to correct its estimates outside of it. Tewari et al. describe this in On Optimality of Adaptive Linear-Quadratic Regulators as getting trapped in regions where the dynamics are unfalsifiable. The system runs smoothly, but suboptimally, incurring linear regret.


Breaking the Trap with Randomized Exploration

To escape this trap, the controller must actively explore. In continuous control, exploration is achieved by adding a small perturbation to the control input, transforming the greedy law into a randomized one:

$$u_t = K(\hat{A}, \hat{B})x_t + \eta_t$$

This perturbation $\eta_t$ acts as a probe. By shaking the system slightly out of its comfort zone, it forces the state to visit new directions, providing the least-squares estimator with the data it needs to fully identify $A$ and $B$.

There are two primary ways to structure this exploration:

  • Thompson Sampling (Randomized CE): Instead of calculating a single point estimate $\hat{A}, \hat{B}$, the controller maintains a posterior distribution over the possible matrices. At the start of a period, it samples a candidate model from this distribution and acts optimally with respect to that sample. As analyzed by Abeille et al. in Thompson Sampling for Linear-Quadratic Control Problems, this naturally balances exploration and exploitation based on the current level of uncertainty.
  • Naive $\epsilon$-Greedy Exploration: Surprisingly, sophisticated posterior sampling is not always necessary. Simchowitz et al. demonstrate in Naive Exploration is Optimal for Online LQR that simply adding pure, independent Gaussian noise directly to a greedy certainty-equivalent controller is minimax optimal. The system's inherent dynamics amplify this noise, providing sufficient excitation to learn the system efficiently.

The Danger of Continuous Adaptation

If injecting noise solves exploration, why not simply update our least-squares estimates $\hat{A}, \hat{B}$ and recompute our control law at every single time step?

While continuous updates work well in purely statistical settings like multi-armed bandits, they introduce a severe hazard in physical control systems: policy switching instability.

When you change a control policy from $K_t$ to $K_{t+1}$, you alter the closed-loop dynamics of the system. If the policy changes at every time step based on minor statistical fluctuations in the data, the system can experience erratic, transient behaviors. The states do not have time to mix or stabilize, which can cause the system to blow up or incur massive "switching costs" that destroy the regret bounds.


The Solution: Lazy Update Schedules

To prevent this instability, modern adaptive control algorithms use lazy update schedules or epoch-based control. Instead of updating the policy continuously, the controller is frozen for a period of time and only updated when a mathematically rigorous "information threshold" is crossed.

The core mechanism behind this threshold is the determinant-doubling trick, first applied to adaptive control by Abbasi-Yadkori et al. in Regret Bounds for the Adaptive Control of Linear Quadratic Systems.

Let $V_t$ be the design matrix (or Gram matrix) of our least-squares regression, which tracks the history of our states and actions:

$$V_t = \lambda I + \sum_{s=1}^{t-1} \begin{bmatrix} x_s \\ u_s \end{bmatrix} \begin{bmatrix} x_s \\ u_s \end{bmatrix}^T$$

The determinant $\det(V_t)$ geometrically represents the volume of the space we have explored so far. It serves as a proxy for our total information. The lazy update rule states: Only update the control policy when $\det(V_t)$ doubles.

Time Step:   1   2   3   4   5   6   7   8   9   10  ...  T
Information: 2 → 2.1 → 2.3 → 4 ───→ 4.2 → 4.5 → 8 ───────→ 16
Policy:      [  Update 1  ]   [   Update 2   ]   [ Update 3 ]

Why This Works

This simple rule provides two vital guarantees that make adaptive control work:

  1. Bounded Policy Switches: Because the determinant grows at most exponentially with the horizon $T$, its determinant can only double roughly $O(\log T)$ times. For example, over a horizon of $T = 100,000$ steps, the controller might only change its policy a dozen times. This drastically minimizes switching costs and ensures physical stability, a property leveraged by Cohen et al. in Learning Linear-Quadratic Regulators Efficiently with only √T Regret.
  2. Guaranteed Information Gain: If the determinant has not doubled, it means the data we are currently collecting is highly redundant with what we already know. Updating the controller would result in a negligible change to our parameter estimates while risking system instability. We only incur the risk of a policy switch when we are guaranteed to receive a substantial, uncertainty-reducing payload of new information.

By pairing randomized exploration with lazy updates, the controller achieves the theoretical lower bound for learning. As shown by Wang et al. in Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamics, this combination guarantees a tight, optimal frequentist regret bound of $\tilde{O}(\sqrt{T})$.


Generalizing the Framework

The core principles of randomized certainty equivalence and epoch-based updates have proven remarkably robust, expanding far beyond the basic stationary LQR problem:

Key Foundational Work

Regret Bounds for the Adaptive Control of Linear Quadratic Systems (2011) — contributed 1 concept elements to this direction.
Thompson Sampling for Linear-Quadratic Control Problems. (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_certainty_equivalence_control_ed080233,
  title = {certainty equivalence control},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/certainty-equivalence-control/rdr_ed080233050d4416ac48d61405e63327},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_certainty_equivalence_control_ed080233_v1,
  title = {certainty equivalence control},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/certainty-equivalence-control/rdr_ed080233050d4416ac48d61405e63327/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake