PaperlayerView exact revision on arXiv

Source-linked AI summary

Naive Exploration is Optimal for Online LQR

Max Simchowitz, Dylan J. Foster

arXiv:2001.09576v4cs.LGmath.OCstat.ML

TL;DR

Online LQR asks how to control an unknown system efficiently and whether sophisticated exploration is necessary. The paper proves matching regret bounds, analyzes Riccati perturbations with the self-bounding ODE method, and shows that naive ε-greedy exploration attains the optimal rate for stabilizable systems.

  • Problem

    The paper studies whether sophisticated exploration strategies are needed for efficient learning in online LQR with unknown system parameters.

  • Method

    The paper combines upper and lower bounds with the self-bounding ODE method to control perturbations of Riccati-equation solutions and analyze certainty equivalent control.

  • Results

    Naive ε-greedy exploration attains asymptotically optimal regret for online LQR, leaving little room for improvement over naive exploration.

  • Takeaways & Limitations

    The optimal regret characterization indicates that sophisticated exploration provides little benefit for online LQR, while the analysis applies to all stabilizable systems.

  • Takeaways & Limitations

    The upper-bound analysis relies crucially on independence of the noise process; extending it to general sub-Gaussian martingale noise would require improved concentration bounds for quadratic forms of martingale vectors.

Abstract

from arXiv · show

We consider the problem of online adaptive control of the linear quadratic regulator, where the true system parameters are unknown. We prove new upper and lower bounds demonstrating that the optimal regret scales as $\widetildeΘ({\sqrt{d_{\mathbf{u}}^2 d_{\mathbf{x}} T}})$, where $T$ is the number of time steps, $d_{\mathbf{u}}$ is the dimension of the input space, and $d_{\mathbf{x}}$ is the dimension of the system state. Notably, our lower bounds rule out the possibility of a $\mathrm{poly}(\log{}T)$-regret algorithm, which had been conjectured due to the apparent strong convexity of the problem. Our upper bound is attained by a simple variant of $\textit{certainty equivalent control}$, where the learner selects control inputs according to the optimal controller for their estimate of the system while injecting exploratory random noise. While this approach was shown to achieve $\sqrt{T}$-regret by (Mania et al. 2019), we show that if the learner continually refines their estimates of the system matrices, the method attains optimal dimension dependence as well. Central to our upper and lower bounds is a new approach for controlling perturbations of Riccati equations called the $\textit{self-bounding ODE method}$, which we use to derive suboptimality bounds for the certainty equivalent controller synthesized from estimated system dynamics. This in turn enables regret upper bounds which hold for $\textit{any stabilizable instance}$ and scale with natural control-theoretic quantities.

1 Introduction

This paper studies whether sophisticated exploration is necessary for online LQR with unknown dynamics. It proves that naive exploration is minimax-optimal, with matching upper and lower bounds that rule out poly(log T) regret and apply to stabilizable systems.

  • Research question: The paper asks whether sophisticated exploration improves online LQR beyond naive ε-greedy exploration or whether exploration is substantially easier than in general reinforcement learning.The question arises because strong convexity might suggest poly(log T) regret, while prior ε-greedy guarantees required controllability.
  • Problem: Online LQR learns unknown linear dynamics while minimizing cumulative quadratic cost relative to the optimal stabilizing controller.The system evolves linearly with stochastic noise, and regret compares the learner's cost with the optimal infinite-horizon linear controller.
  • Lower bound: Theorem 1 proves that every algorithm suffers regret at least eΩ(√(d_u^2 d_x T)) on some nearby instance, ruling out poly(log T) regret.The lower bound resolves the conjecture that strong convexity could yield logarithmic regret in online LQR with unknown dynamics.
  • Upper bound: Theorem 2 shows that certainty-equivalent control with continual ε-greedy exploration attains regret at most eO(√(d_u^2 d_x T)) for every stabilizable instance.This upper bound matches the lower bound's dimension dependence and does not require controllability.
  • Conclusion: The resulting rate is asymptotically minimax-optimal, leaving little room for improvement over naive exploration in online LQR.The paper also notes that the optimal regret contrasts with logarithmic rates available in some strongly convex online-learning settings.
  • Analysis: The self-bounding ODE method controls perturbations of Riccati equations and yields bounds depending on natural control-theoretic quantities rather than explicit spectral-radius or strong-stability parameters.The technique applies to stabilizable systems, including systems that are not controllable, and supports both the upper and lower-bound analyses.

2 Main Results

The paper establishes matching lower and upper bounds for online LQR, showing that naive certainty-equivalent exploration achieves the optimal regret dimension dependence. The analysis applies to stabilizable systems and uses the self-bounding ODE method to control Riccati perturbations.

  • Lower Bound: The lower bound rules out poly(log T)-regret by showing that near-optimal control leaves a dxdu-dimensional parameter subspace insufficiently explored.The resulting control-identification tension forces deviations from the optimal controller and yields an Ω(√(d_u^2 d_x T)) lower bound in the stated regime.
  • Lower Bound: The local minimax lower bound depends on nominal-instance control-theoretic quantities, including operator norm bounds and the singular values of the closed-loop dynamics.Its alternative instances approach the nominal system as T grows, and the dimension parameter m can be tuned instance by instance.
  • Upper Bound: The upper-bound analysis decomposes regret into controller suboptimality, exploratory-noise cost, and lower-order fluctuation terms controlled using the Hanson-Wright inequality.The exploratory noise contributes dependence on d_u, while random cost fluctuations contribute a square-root dimension factor under independent noise.
  • Upper Bound: Certainty equivalent control with continual ε-greedy exploration achieves regret at most eO(√(d_u^2 d_x T)), matching the lower bound up to logarithmic and control-theoretic factors.The algorithm estimates the system with projected least squares, synthesizes an optimal controller for the estimate, and injects white Gaussian exploration noise in epochs.
  • Consequences for Strongly Stable Systems: For strongly stable systems, the specialized upper and lower bounds are nearly matching, with differences limited to polynomial stability factors and a lower-bound singular-value factor.The upper bound also contains a lower-order (d_x+d_u)^2 term that the paper leaves without a complementary lower bound.

3 Perturbation Bounds via the Self-Bounding ODE Method

The paper develops the self-bounding ODE method to control how Riccati solutions and optimal controllers change under system perturbations. This yields perturbation bounds for stabilizable systems that depend on natural value-function quantities rather than explicit spectral-radius or controllability parameters.

  • Method: The self-bounding ODE method controls perturbations of the DARE solution P∞(A, B) and controller K∞(A, B) as system matrices vary.It provides a general recipe for perturbation bounds of solutions to implicit equations.
  • Perturbation bounds: The perturbation guarantee can be certified using approximate system estimates, while avoiding explicit dependence on spectral radius, strong stability, or controllability parameters.The stronger theorem replaces the admissibility condition with one certifiable from an approximate estimate.
  • Perturbation bounds: If ϵop ≤ 1/Csafe(A⋆, B⋆), then the perturbed value matrix remains controlled and the optimal-controller difference is bounded in operator norm.The theorem applies to stabilizable systems and uses ∥P⋆∥op in the stated bounds.
  • Method: The method interpolates between nominal and alternate matrices, establishes smooth Riccati solution curves, and bounds their derivatives through Lyapunov equations.The mean value theorem then converts uniform derivative bounds into perturbation bounds.
  • Self-bounding property: A self-bounding derivative property ensures that bounded P(t) prevents P′(t) from escaping, allowing the solution curve to remain well behaved.The argument compares the vector-valued ODE with a scalar ODE whose growth is governed by the same self-bounding function.
  • Self-bounding property: For g(z) = cz^p, the method guarantees bounded solutions and derivatives when α = c(p − 1)∥y(0)∥^(p−1) < 1.The resulting bounds scale as (1 − α)^−1/(p−1) for the solution and (1 − α)^−p/(p−1) for its derivative.

4 Proof of Lower Bound (Theorem 1)

The lower-bound proof constructs many nearby LQR instances and shows that low regret requires accurate controller identification. Information-theoretic indistinguishability then forces either substantial exploration or substantial regret on an alternative instance.

  • Instance construction: The proof packs alternate systems around a nominal stabilizable instance and uses controller perturbations to encode a hypercube of alternatives.A sufficiently large packing is needed to obtain the correct dimension dependence.
  • Instance construction: For non-degenerate closed-loop dynamics, the optimal-controller distance between the nominal and perturbed systems is Ω(∥∆∥F) to first order.This links system perturbations to distinguishable controller changes.
  • Low regret and estimation: Low regret implies that the learner’s controls stay close to the optimal controller for each alternative instance.The proof formalizes this through the deviation quantity K-Erre[π].
  • Low regret and estimation: When the deviation from an alternative controller is small, least squares can estimate that controller from the first T/2 rounds.The estimator is then used to recover the encoded hypercube index.
  • Information-theoretic tradeoff: The exploration error K⋆-Erre[π] measures deviation from the nominal controller, whereas K-Erre[π] measures deviation from the alternative controller.Their relationship produces the proof’s exploration-versus-identification tradeoff.
  • Information-theoretic tradeoff: Either average exploration error is at least n ϵpack^2/4, or the alternative-controller regret proxy is large.Assouad-style arguments show that distinguishing neighboring instances requires controls that deviate from the nominal optimal policy.

5 Algorithm and Proof of Upper Bound (Theorem 2)

The upper-bound algorithm combines certainty-equivalent control with continual random exploration and epoch-wise least-squares estimation. Perturbation and concentration arguments show that this strategy achieves a regret decomposition with a leading square-root-in-T term and lower-order logarithmic terms.

  • Algorithm: Algorithm 1 uses doubling epochs, estimates system dynamics by ordinary least squares, and tests whether the estimate is close enough for perturbation guarantees.It starts from a stabilizing controller and switches to an estimated optimal controller only after the closeness test succeeds.
  • Algorithm: When the estimate is certified, the algorithm plays the certainty-equivalent controller with exploratory noise whose scale balances exploration and exploitation.Before certification, it falls back to the stabilizing controller with constant-scale exploratory noise.
  • Proof structure: The proof uses a common Lyapunov function and high-probability safe, bounded, regret, and least-squares events to control the algorithm’s epochs.The Lyapunov argument avoids complications from sequential strong stability.
  • Proof structure: The regret decomposition separates controller-suboptimality, controller-switching, exploratory-noise, stochastic-fluctuation, and poly(log T) components.The switching term is lower order, while the exploratory-noise and fluctuation terms contribute to the leading square-root-in-T behavior.
  • Proof structure: The estimator becomes correct after the safe epoch, enabling perturbation bounds to control the suboptimality of certainty-equivalent controllers.The resulting analysis combines estimation error bounds with the epoch-wise regret decomposition.
  • Final bound: The final high-probability regret bound consists of a component scaling with √T and a lower-order component scaling with log T.The initial rounds and failure events are incorporated into the final bound with total probability at least 1 − δ.

6 Conclusion

The paper establishes asymptotically optimal online-LQR regret and develops perturbation tools supporting guarantees for stabilizable systems.

  • ε-greedy exploration attains the asymptotically optimal regret rate for online LQR.
  • The perturbation theory applies to stabilizable systems and controls changes in Riccati solutions and synthesized controllers.
  • Theorem 5 bounds the perturbed cost matrix by 1.0835∥P⋆∥op and bounds controller deviation after multiplication by B⋆.
  • The analysis also establishes common Lyapunov-function and H∞-norm controls for perturbed closed-loop systems.
  • The self-bounding ODE method is used to derive perturbation bounds, while ordinary least squares tools support both upper- and lower-bound proofs.

B.4.2 Proof of Proposition 7

This proof develops covariance and value-function perturbation controls by interpolating between controllers and applying the self-bounding ODE method.

  • The proof compares the optimal controller with a perturbed controller through the interpolation eK(t) = K⋆ + t∆K.
  • The covariance derivative satisfies ∥Σ′(t)∥op ≤ 2∥Σ(t)∥5/2∥B⋆∆K∥op.
  • When the controller perturbation is sufficiently small, the self-bounding ODE method controls covariance growth along the interpolation.The stated condition includes ∥B⋆∆K∥op < 1 relative to the initial covariance scale.
  • The resulting covariance bound gives ∥Σ(1)∥op ≤ 2∥Σ(0)∥op under the stated small-perturbation condition.
  • The proof uses differentiability of the DARE solution and Lyapunov equations to express derivatives of P(t) and K(t).

C.3.2 Proof of Lemma 3.2 and Lemma B.2

This section bounds derivatives of the optimal controller and cost matrix using the Riccati derivative identities and norm estimates for closed-loop perturbations.

  • The derivative calculations support perturbation bounds for the closed-loop dynamics and cost quantities.
  • The analysis preconditions controller derivatives with matrices involving R0 = Ru + B⊤PB to obtain norm bounds.
  • Bounds on K′ and K′′ are obtained by differentiating the Riccati controller formula and controlling the resulting terms with the established norm estimates.
  • The second derivative of the cost matrix satisfies ∥P′′∥◦ ≤ poly(∥P⋆∥op)ϵopϵ◦.

D Self-Bounding ODE Method

The self-bounding ODE method converts differential inequalities into uniform bounds, and the appendix also develops least-squares tools used in the main proofs.

  • Self-Bounding ODE Method: Theorem 13 provides a generic guarantee for self-bounding ODEs by comparing a vector solution with a scalar ODE.
  • Self-Bounding ODE Method: The comparison argument yields ∥v(t)∥ ≤ w(t) whenever the scalar comparison solution dominates the vector derivative growth.
  • Self-Bounding ODE Method: The method establishes continuation to the full interval by showing that the implicit solution cannot terminate while the comparison bound remains finite.
  • Self-Bounding ODE Method: For self-bounding functions with polynomial growth g(z) = cz^p, Corollary 3 gives an explicit bound on ∥y(t)∥ over t ∈ [0, 1].
  • Least-Squares Tools: The appendix defines a martingale least-squares setup and develops self-normalized, Frobenius, and two-scale estimation bounds.
  • Least-Squares Tools: The two-scale OLS bound accounts for cross-subspace interactions through the term ∥PΛ(1 − P)∥op.

E.4.1 Proof of Lemma E.4

The proof establishes a high-probability control bound by combining a martingale small-ball property, matrix concentration, and trace-based simplifications.

  • Small-ball property: The sequence (z_t) satisfies a (1, Σ, 3/10)-block martingale small ball property via the Paley–Zygmund inequality.This invokes the variant in Simchowitz et al. (2018, Equation 3.12) and their Definition 2.1.
  • Concentration bound: For any positive semidefinite Λ+, the proof applies a concentration result with the normalization factor T corrected.The resulting expression includes dimension, confidence, and log-determinant terms.
  • Probability control: Markov’s inequality and ∥Λ∥op ≤ tr(Λ) convert the trace control into a probability bound for Λ not being dominated by Λ+.The argument is restricted to the event E and uses a positive semidefinite comparison matrix.
  • Parameter choice: Balancing the confidence-dependent terms selects δ = a^(1/(d+1)), after which tr(ΛT) ≤ JT completes the bound.The final simplification uses the assumed trace bound and elementary algebra.

F.2 Proof of Lemma 4.3

The proof characterizes finite-horizon optimal LQR policies and decomposes regret into policy and comparator suboptimality, while bounding the resulting error sequence geometrically.

  • Regret decomposition: Regret is compared with the true optimal policy and decomposed into policy suboptimality and comparator suboptimality.The proof compares both costs to the value of the optimal policy starting from x_1 = 0.
  • Optimal finite-horizon control: The optimal policy π⋆ is defined by minimizing the finite-horizon Q-function at each time step.Its action is u_t := arg min Q_t;T(x_t, u).
  • Optimal finite-horizon control: The finite-horizon value function is quadratic, and Q_t;T(x,u) − V_t;T(x) equals the squared deviation from the optimal linear controller.The controller is represented by K_{T−t} and the value function by P_{T−t}.
  • Comparator suboptimality: The comparator’s finite-horizon contribution is controlled using the infinite-horizon cost of K⋆, whose horizon-T regret is bounded by T times that cost.The resulting comparison is used together with the performance difference lemma.
  • Geometric error decay: The error sequence η_t decreases geometrically for every stabilizable system.Lemma F.7 states this for η_t defined in the proof, with rate parameter ν = 2∥P∞(A,B)∥op Ψ(A,B)^2.
  • Riccati recursion: The Riccati recursion converges to the unique DARE solution when R_x and R_u are positive definite.The cited bound includes a correction involving ∥P∞∥op.

F.3 Proof of Lemma 4.4

The proof bounds estimation and controller errors through thresholded least squares, KL-divergence comparisons, and a comparison trajectory under optimal inputs.

  • System estimation: A thresholded least-squares estimator is introduced to estimate the unknown system matrices.The estimator is defined with a tunable constant chosen later in the proof.
  • Information-theoretic comparison: The lower-bound argument compares laws induced by paired systems over the first τ = T/2 rounds and controls their distinguishability using total variation and KL divergence.Randomized algorithms are reduced to deterministic ones for the KL analysis by conditioning on random seeds.
  • Information-theoretic comparison: For the paired systems, the conditional state distributions are Gaussian, so the KL divergence is expressed through differences in their conditional means and summed over time.The control input is deterministic conditional on the past filtration.
  • Controller error: The proof relates controller error to regret and obtains E_e[K-Erre[π]] ≤ 2E_e[Regret_e[π]] + γ_err ≤ 2γ_errT.The final displayed bound further upper-bounds this quantity by T 3 d_x Ψ⋆^3.
  • Comparison trajectory: A comparison sequence uses the optimal infinite-horizon inputs for each system, and the state difference is driven by the controller perturbation term B_eδ_t.The proof bounds the resulting operator norms using Lyapunov and Riccati quantities.
  • Comparison trajectory: The Lyapunov operator bound scales as T^2∥P_e∥op for the closed-loop system.This estimate is used to control the comparison sequence over the finite horizon.

F.7 Additional Corollaries of Theorem 1

For scaled identity systems, the corollary removes a restriction on the input dimension and derives system-specific Riccati and closed-loop bounds.

  • Scaled identity systems: For scaled identity systems, the requirement d_u ≤ (1 − Ω(1))d_u can be removed.This is the stated additional consequence for the specialized system family.
  • Scaled identity systems: If A⋆ = (1−γ)I, B⋆ = U⊤ with orthonormal columns, and R_x = R_u = I, the corollary applies for sufficiently large T.The stated condition is T ≥ c_1γ^−p.
  • Riccati quantities: The proof establishes Ψ⋆ ≤ 1 and ∥P⋆∥op ≤ γ^−1 for the scaled identity construction.It also lower-bounds the smallest closed-loop singular value in terms of γ.
  • Riccati quantities: The DARE decouples into scalar equations along the columns of U and their orthogonal complement.The scalar parameters p and k satisfy the displayed relations in Equation (F.7).
  • Riccati quantities: The closed-loop minimum singular value is bounded below by a/(1+p) in the scalar reparameterization a = 1−γ.This bound follows from the two closed-loop eigenvalue cases considered in the proof.
  • Safe estimated systems: The proof concludes by comparing the Riccati solution of the safe estimated system with P⋆ in both operator-norm directions.The comparison uses Lemma B.6 and Theorem 11 after the projection step.

G.2 Proof of Main Regret Decomposition (Lemma 5.2)

The proof develops a general regret decomposition for control evolution distributions, then bounds its cost and covariance terms using Lyapunov characterizations, projections, and two-scale estimation.

  • Regret decomposition: The resulting regret decomposition combines bounded cost contributions with stability-controlled Lyapunov quantities on the safe event.On Esafe, the proof controls ∥Pk∥op and related closed-loop quantities by natural instance-dependent parameters.
  • Control evolution: The analysis models control evolution under a stabilizing controller, exploratory input noise, and Gaussian process noise.The distribution D(K, σu, x1) specifies the initial state and subsequent dynamics, with wt and gt standard Gaussian vectors.
  • Cost characterization: Quadratic costs are characterized through RK, AK, PK, and JK, enabling expectation and high-probability bounds.The characterization permits arbitrary positive semidefinite cost matrices and defines JK as tr(PK).
  • Estimation guarantees: Two-scale least-squares estimation and union bounds establish simultaneous covariance and confidence guarantees across rounds.The argument invokes the two-scale OLS estimate and reparameterizes failure probabilities to control multiple rounds and dimensions.
  • Covariance geometry: Round-wise projections separate controller-aligned directions from their orthogonal complement for covariance analysis.Vk contains vectors satisfying vx + bKkvu = 0, while Pk and P⊥k project onto Vk and its orthogonal complement.
  • Covariance geometry: The proof lower-bounds centered covariances in both projected subspaces and converts these bounds into Loewner-order guarantees for Λk.The resulting covariance lower bound has separate coefficients for Pk and P⊥k.

G.4.3 Proof of Lemma G.5

The proof bounds a round-wise covariance term by decomposing it into three contributions, representing the principal term as a Gaussian quadratic form and applying covering and concentration arguments.

  • Setup: The round is analyzed through accumulated contributions from previous steps, with covariates expressed as linear functions of jointly Gaussian noise.The relevant perturbation state is linear in the process and input-noise vector.
  • Covering argument: Covering nets over the left unit ball and controller-induced right subspace reduce uniform covariance control to finitely many vector pairs.The right net spans vectors formed from state and controller-linked input components.
  • Quadratic-form control: The principal contribution is a quadratic form in Gaussian noise with a matrix of rank at most τk.The matrix representation follows from block-diagonal rank-one terms and linear operators mapping noise to covariates.
  • Quadratic-form control: Hanson–Wright bounds control the quadratic-form fluctuations after bounding trace, Frobenius, and operator norms.The proof constructs a positive semidefinite comparison matrix and separately bounds its components.
  • Concentration: The remaining contributions are controlled using Gaussian tail and operator-norm bounds, then combined with union bounds over the covering nets.For the third term, τk ≥ du + log(1/δ0) yields term3 ≲ √τk.
  • Concentration: When τk is sufficiently large relative to dimension and instance-dependent thresholds, the combined covariance bound holds with probability 1 − δ0.The proof states this after combining the three term bounds and imposing conditions involving dx + du and ΨB⋆J0∥P⋆∥op^3/2.

G.5 Proof of Lemma 5.5 (k < ksafe)

For rounds before ksafe, the proof couples the actual trajectory to a nominal exploratory trajectory, establishes confidence and covariance bounds, and controls the resulting costs through Gaussian quadratic forms.

  • Pre-safe coupling: Before ksafe, the proof analyzes rounds preceding the least-squares procedure’s safe-control phase.The coupled nominal sequence uses the same process noise and random perturbations as the actual sequence.
  • Pre-safe coupling: The coupled trajectory coincides with the actual trajectory before τksafe, allowing confidence quantities to be analyzed on the nominal sequence.The corresponding OLS estimators and covariance matrices are introduced for this purpose.
  • Confidence control: A lower covariance bound and trace upper bound yield valid confidence intervals with high probability.The argument uses Gaussian-system covariance properties, Lyapunov quantities, and union bounds across rounds.
  • Safe-control threshold: Before safe control begins, uncertainty cannot fall below a threshold determined by the safety conditioning quantity.For Λk ⪰ I, the proof obtains Confk ≳ ϵsafe, with ϵsafe depending on ∥P⋆∥op.
  • Cost control: The initial-phase cost is represented as a Gaussian quadratic form and bounded using expectation estimates and Hanson–Wright concentration.The construction defines Lyapunov-based cost parameters and combines quadratic-form bounds with initial-state terms.
  • Cost control: The proof also develops Toeplitz and covariate representations to bound the resulting quadratic-form matrices.Toeplitz operator norms are controlled by H∞ norms, while cross terms are bounded using matrix factorization and Young’s inequality.
Loading 2001.09576v4…