Statistical Learning Theory for Control: A Finite Sample Perspective

IDENTIFICATION

• Finite-sample tools characterize identification-error tails, including a sharp log 1/δ sample dependence, and can cover nonstationary systems and dimensions that grow with sample size.The analysis does not fully characterize the finite-sample error distribution, and its bounds may be less sharp asymptotically because universal constants can be large.Source: IDENTIFICATION · p. 3

From Asymptotics to Finite Sample Guarantees

• Finite-sample guarantees expose burn-in and failure-probability effects, while raising questions about dependent, control-affected data, exploration and exploitation, and system-specific learnability.They offer qualitative insight into learning difficulty, though often at the expense of asymptotic sharpness; the survey also seeks a common language across control, learning theory, and statistics.Source: From Asymptotics to Finite Sample… · p. 4

Fully Observed Systems

• For fully observed systems with no measurement noise, the section focuses on estimating A⋆ and B⋆ from a single trajectory using least squares.The same techniques can also be applied to estimating the process-noise covariance Σw.Source: Fully Observed Systems · p. 5

Persistency of excitation

• Persistency of excitation requires the Gram matrix’s minimum eigenvalue to grow, while small-ball methods provide a one-sided lower bound without stability-dependent two-sided concentration.The analysis assumes non-explosive dynamics, Gaussian open-loop inputs, and full-rank process noise; indirect excitation can also suffice when the controllability structure is well-defined. The minimum sample size for the relevant condition is the burn-in time.Source: Persistency of excitation · pp. 5–6

Sample Complexity Upper Bounds

• The least-squares estimator admits instance-specific sample-complexity upper bounds, with the time index trading a stronger lower bound for increased burn-in.A larger time index strengthens the lower bound, while the required burn-in grows linearly with the index.Source: Sample Complexity Upper Bounds · p. 6

Self-normalized term

• For non-explosive systems, the self-normalized bound grows at most logarithmically with the estimation horizon and nearly matches the independent-sample linear-regression rate.The passage states that the bound is satisfied for sufficiently large T.Source: Self-normalized term · p. 6
• The self-normalized martingale structure arises because process noise is independent of the state and input, while larger covariates compensate for increases in the accumulated term.The term is self-normalized through the increase in V^(-1/2) as covariates grow.Source: Self-normalized term · p. 6

Persistency of excitation and small-ball bounds

• A block small-ball condition requires a nonzero block-average probability of being away from the origin, with Γlb capturing the geometry of the lower bound.Persistency of excitation can be established through one-sided lower bounds on the Gram matrix's least singular value.Source: Persistency of excitation and… · p. 7

LINEAR SYSTEMS

• Under white-noise inputs, the stacked state-and-input process satisfies a block martingale small-ball condition with parameters (k, ˜Γ⌊k/2⌋, 3/20).The signal-to-noise ratio depends on the system's controllability structure.Source: LINEAR SYSTEMS · p. 7
• Ignoring logarithmic terms, sample complexity grows as 1/ε^2 and linearly with the unknown dimension, while also depending inversely on signal-to-noise ratio and logarithmically on δ.The dimension dependence reflects the number of unknown entries in A⋆ and B⋆ relative to the number of state measurements.Source: LINEAR SYSTEMS · p. 7
• For indirectly excited states, persistency of excitation can still hold when ˜Γ⌊τ/2⌋ is nonzero, with ⌊τ/2⌋ selectable as the controllability index.The upper bound is instance-specific; class-wide guarantees require global norm bounds and a bound on λ^-1_max(Γτ).Source: LINEAR SYSTEMS · p. 7

Confidence ellipsoids

• The stated guarantees are qualitative and data-independent, depend on unknown system quantities, and use an operator norm that reflects the direction of largest error.With isotropic or nonsingular noise, Γ1 ⪰ Σw ≻ 0 and τ = 2 suffices for the burn-in condition and sample-complexity bound.Source: Confidence ellipsoids · p. 7

EXTENSION TO VECTOR PROCESSES

• Projecting vector noise onto an ε-net of directions extends the scalar self-normalized martingale bound, with a union bound controlling all directions.A finer net reduces discretization error but increases the number of points; ε = 1/2 is a typical choice.Source: EXTENSION TO VECTOR PROCESSES · p. 8, BOUNDS FOR SCALAR PROCESSES · p. 8

BOUNDS FOR SCALAR PROCESSES

• Data-dependent confidence ellipsoids adapt to observed excitation, but their radius does not directly reveal the statistical rate and the resulting balls can be conservative in some directions.The ellipsoids can be sharper using a data-based covariance estimate or upper bound for ∥Σw∥op.Source: BOUNDS FOR SCALAR PROCESSES · p. 8

Sample Complexity Lower Bounds

• Information-theoretic lower bounds show least squares is near-optimal for fully observed systems: the 1/ε^2 rate, dimension factor dx, and confidence log 1/δ are fundamental.The argument constructs hard-to-identify systems and applies information-theoretic inequalities.Source: Sample Complexity Lower Bounds · p. 9
• A gap remains between upper and lower bounds in general, but it can be closed for stable systems at the cost of burn-in depending on mixing time; it can also be made small for diagonalizable marginally stable systems when τ = Θ(T).For stable systems, the burn-in depends on 1/(1 − ρ(A⋆)).Source: Sample Complexity Lower Bounds · p. 9
• With active exploration based on sinusoidal inputs, least squares attains the minimax lower bound asymptotically as δ → 0.Finding an optimal exploration policy is difficult because it requires knowledge of system dynamics.Source: Sample Complexity Lower Bounds · p. 10
• For sparse systems, ℓ1-regularized identification under mutual incoherence has sample complexity scaling with the number of nonzero parameters, while improving the dependence on sparsity remains open.Extending these results to open-loop non-explosive systems is also an open question; the stated burn-in depends on a stabilizing gain known a priori.Source: Sample Complexity Lower Bounds · p. 10

Summary and Generalizations

• With multiple trajectories, learning can be more efficient when Ntraj = Ω(d) than when Ntraj = o(d), suggesting more trajectories may be preferable to a longer horizon at fixed total samples.The cited unified treatment gives parameter-recovery guarantees in expectation, so they are not included in the table summarized in the passage.Source: Summary and Generalizations · p. 10
• Full-rank process noise supports polynomial sample complexity, whereas degenerate noise can yield exponential dependence on dimension; Hanson-Wright bounds also degrade near instability because burn-in grows with mixing time.Small-ball techniques remain applicable at ρ(A⋆) = 1, unlike the stability-dependent Hanson-Wright approach.Source: Summary and Generalizations · p. 10

Birgé’s Inequality

• Birgé’s inequality, a sharper version of Fano’s inequality, gives a tool for lower bounds in multiple testing, where successful identification requires sufficiently distinguishable distributions.The section uses separated systems with similar data distributions to construct difficult identification problems.Source: Birgé’s Inequality · p. 11, SYSTEM IDENTIFICATION · p. 11

SYSTEM IDENTIFICATION

• Finite-sample guarantees can allow martingale-difference process noise, but the methods remain fragile to this assumption and sharply handling colored noise is challenging in general.For heavy-tailed noise, least squares may be optimal in expectation but not in deviation; the survey reports no sharp characterization of system-identification failure probabilities in that setting.Source: SYSTEM IDENTIFICATION · p. 12

Partially Observed Systems

• For partially observed systems, state-space parameters are not uniquely identifiable because similarity transformations preserve the input-output map.The survey focuses on the subspace/realization approach, which estimates Hankel matrices before realization; prediction-error methods instead optimize over system parameters.Source: Partially Observed Systems · p. 12

Regression Step

• The regression step expresses future outputs as a linear function of past inputs and outputs, with a bias that decays exponentially as the past horizon grows.Self-normalized martingale methods and persistence-of-excitation arguments support the analysis; lifting to an unstructured Gp yields a sample-complexity bound scaling with p(dy + du), trading a larger horizon against reduced bias.Source: Regression Step · pp. 13–14

Realization

• Realization uses Hankel-matrix SVD to recover observability and controllability matrices from Markov parameters, up to a similarity transformation.For noisy estimates, the required robustness condition is that Markov-parameter error be smaller than the true Hankel matrix’s smallest singular value; this can impose high sample complexity.Source: Realization · p. 14

Isometry for Hankel Matrices

• Hankel matrices built from past-L-step data arise in prediction, and small-ball methods offer one route to assessing whether they are persistently exciting.The survey also reviews a stronger two-sided result for this analysis.Source: Isometry for Hankel Matrices · p. 15

Overview and Limitations

• For partially observed systems, lower bounds lack transparent expressions in system-theoretic quantities; finite-sample analogs of some asymptotic optimality results and identification of explosively unstable systems remain open.Two-step procedures guarantee learnability for non-explosive systems, but whether they extend to explosively unstable systems is open.Source: Overview and Limitations · p. 16

OFFLINE CONTROL

• Optimal sample complexity for partially observed systems remains an open question, including whether finite-sample analyses can match asymptotic performance and how complexity depends on model order and system parameters.The open problem also asks about the unknown-order case.Source: OFFLINE CONTROL · p. 16

Certainty Equivalence

• Certainty-equivalent control uses estimated dynamics as if they were true, but its guarantee requires sufficiently accurate estimates to establish stability on the actual system.For almost every input-state experiment, least squares with certainty-equivalent control is optimal up to universal constants.Source: OFFLINE CONTROL · p. 17, Certainty Equivalence · p. 17

Model-Based Methods

• Combining identification bounds with certainty-equivalent control gives an offline LQR suboptimality gap of at least ˜O(1/Ntot), provided the estimated controller stabilizes the true system.That condition may require a large burn-in time.Source: Model-Based Methods · p. 17

Robust Control Methods

• Robust control can stabilize every system consistent with coarse estimates and error bounds, whereas certainty-equivalent control may not be stabilizing in that setting.The survey discusses finite-sample robust control and an SLS scheme using model-error information.Source: Robust Control Methods · p. 17

Riccati Equation Perturbation Theory

• Operator-theoretic perturbation analysis relates errors in estimated dynamics to errors in Riccati quantities, while robust controllers have worse suboptimality guarantees than certainty-equivalent control.An alternative ODE approach is reported to give tighter bounds in system-theoretic parameters.Source: Riccati Equation Perturbation Theory · p. 18

Policy Gradient Methods

• For LQR, gradient descent reaches an ϵ-accurate controller in O(log 1/ϵ) iterations when initialized at a stabilizing controller; the cost is not finite for non-stabilizing controllers.A more sophisticated gradient strategy can remove the stabilizing-initialization assumption.Source: Riccati Equation Perturbation Theory · p. 18

Model-Free Methods

• Model-free methods use essentially no structural information about the problem, and policy-gradient methods apply gradient descent to a controller parameterization of the LQR cost.In the state-feedback setting, the described parameterization uses controllers ut = Kxt.Source: Model-Free Methods · p. 18, Policy Gradient Methods · p. 18

Fundamental Limits and Model-Based versus Model-Free

• In a simplified LQR setting, certainty equivalence outperforms REINFORCE by a polynomial gap in problem dimension in sample complexity.The comparison uses asymptotically exact risk expressions and assumes R = 0 and K⋆= −B†⋆A⋆.Source: Fundamental Limits and Model-Based… · pp. 18–19
• Regret measures cumulative suboptimality against the Riccati-computable optimal policy and reflects the exploration–exploitation trade-off; low regret requires sufficiently rich experiments.The survey emphasizes statistical analysis rather than robustness aspects of adaptive methods.Source: Fundamental Limits and Model-Based… · p. 19

ONLINE CONTROL

• For state-feedback systems, certainty equivalence with additive Gaussian exploration attains the stated high-probability guarantee when the horizon is sufficiently large.The required horizon is polynomial in dimension and system-dependent quantities.Source: ONLINE CONTROL · p. 19

T QTxT +

• The regret-rate result settles the optimal dependence on system dimensions and horizon, with a matching lower bound and the same rate in expectation up to logarithmic factors.The exact rate is not present in the supplied passages.Source: T QTxT + · p. 19
• The optimal dependence of regret on P⋆ and other system-theoretic quantities remains open, with a polynomial gap between known upper and lower bounds in P⋆.The section points to Table 3 for a summary of state-feedback and partially observed results.Source: T QTxT + · p. 19, Table 3 · p. 20

Certainty Equivalence

• A stabilizing initialization lets gradient descent updates remain stable and converge to the global optimum.The objective is not convex, but the passages state that it satisfies the Polyak-Łojasiewicz condition under controllability and is sufficiently regular.Source: Certainty Equivalence · p. 20
• Online certainty equivalence repeatedly estimates the dynamics, solves the Riccati recursion as if those estimates were true, and applies the resulting controller.The approach is also the key algorithmic idea identified for LQR regret minimization.Source: Certainty Equivalence · pp. 19–20
• Under an optimal linear feedback policy, distinct dynamics can produce identical closed-loop systems, so perturbing inputs is needed for parameter identification.The resulting lack of closed-loop identifiability can make the least-squares error diverge near the optimal policy.Source: Certainty Equivalence · p. 21
• An i.i.d. sequence of rescaled isotropic noise with standard deviation t^-α is sufficient to guarantee parameter recovery, with operator-norm error ∥bθ_t−θ⋆∥_op = ˜O(t^(α−1/2)).Source: Certainty Equivalence · p. 21

Optimism and Thompson Sampling

• The tightest proven regret bounds to date use simple input perturbations, rather than the more sophisticated optimism or Thompson-sampling strategies.The supplied passages describe optimism and Thompson sampling as alternative exploration strategies.Source: Optimism and Thompson Sampling · p. 22

Regret Lower Bounds

• For state-feedback regret, the optimal dependence on P⋆ remains unresolved: known upper bounds have a polynomial gap from lower bounds.The passages also state that tight scaling in P⋆ is unavailable.Source: Regret Lower Bounds · p. 23
• The lower-bound argument links regret to Fisher information: low regret constrains experiment design and limits how quickly the dynamics can be identified.The passages describe regret as an upper bound for Fisher information and as a constraint on available experiment designs.Source: Regret Lower Bounds · p. 23
• A memoryless subsystem paired with an integrator yields P⋆ on the order of 2^dx, illustrating exponential system complexity in dimension.The integrator component can amplify errors from misspecification in the coupling between the otherwise decoupled subsystems.Source: Regret Lower Bounds · p. 23
• More generally, the controllability index—the steps needed to reset a noise-free system—can determine local minimax regret with exponential dependence.The survey concludes that learning to control can be exponentially complex even for examples as simple as integrators.Source: Regret Lower Bounds · p. 24

Partially Observed Systems

• The learner in a partially observed setting has access to measured outputs rather than the system state.The passage contrasts this setting with state feedback.Source: Partially Observed Systems · p. 24
• The survey characterizes its understanding of the state-feedback setting as relatively complete.The passage contrasts that status with the lesser understanding of partially observed systems.Source: Partially Observed Systems · p. 24
• The time-scaling result for state feedback is introduced as a comparison point, but its value is not stated in the supplied passage.The passage ends before giving the scaling.Source: Partially Observed Systems · p. 24

Regret Bounds for Partially Observed Systems

• The partially observed setting lacks a known correct dimensional scaling, and current approaches do not handle the general LQG cost structure.The cited approach instead applies to a narrower criterion.Source: Regret Bounds for Partially Observed… · p. 24
• A properly tuned disturbance-feedback controller combines exploratory data collection, Markov-parameter estimation, and online gradient descent to obtain a regret guarantee for partially observed systems.The approach uses an initial exploration period, then estimates Markov parameters and uses them to run projected gradient descent on controller parameters.Source: Regret Bounds for Partially Observed… · p. 24
• A worst-case regret lower bound is unavoidable for instances with large input dimension.The passage identifies this as a worst-case result; it does not give the complete rate in the supplied text.Source: Regret Bounds for Partially Observed… · p. 24

Disturbance Feedback Control

• For an alternative comparator—the best persistently exciting policy—logarithmic regret is possible, but the optimal LQG policy need not be persistently exciting.The relation between this regret definition and the optimal-policy comparator remains open.Source: Disturbance Feedback Control · p. 24
• The sketched disturbance-feedback approach requires ρ(A⋆) < 1, although it can be extended to open-loop unstable systems.For stable systems, the error signal decays exponentially fast to zero.Source: Disturbance Feedback Control · p. 24
• When B⋆ is known, identifying A⋆ suffices and can yield logarithmic regret against the optimal controller.The claim is for the state-feedback setting with B⋆ known a priori.Source: Disturbance Feedback Control · p. 25
• Online prediction can attain logarithmic regret because prediction has no control-cost objective and does not require persistence of excitation.This is contrasted with online LQR, where exploratory signals affect control cost.Source: Disturbance Feedback Control · p. 25

Control Oriented Identification

• The section asks whether the hardest-to-identify direction necessarily affects control design, rather than whether every parameter must be recovered.It frames this as an open question about the connection between identification error and control objectives.Source: Control Oriented Identification · p. 25
• In the example, identifying α becomes harder as β shrinks, yet K = 0 stabilizes the system without knowing α.Thus, the example's identification complexity grows with β^-1 while stabilization remains trivial.Source: Control Oriented Identification · p. 25

SUMMARY AND DISCUSSION

• The survey describes a relatively complete picture of finite-sample system identification and regret minimization for fully observed linear dynamical systems.It also identifies partially observed extensions as an area with substantial work remaining.Source: SUMMARY AND DISCUSSION · p. 25
• Some systems make stabilization depend on identifying α, including its sign, so the worst identification direction can determine stabilization complexity.The example has marginally stable first-state dynamics; the authors characterize such systems as pathological and leave conditions for avoiding them open.Source: SUMMARY AND DISCUSSION · p. 26

Learning with Structure and Regularization

• LASSO can avoid polynomial dependence on state dimension, but its rate degrades with system stability, while the minimax rate over sparse systems is noted as a separate benchmark.The passage also observes that ordinary linear regression can be sample-inefficient or intractable in high dimensions.Source: SUMMARY AND DISCUSSION · p. 26
• Sparse, low-order, and physical properties such as passivity can serve as structural priors, but no finite-sample analysis is available for the nuclear-norm-regularized estimator.The nuclear norm is proposed to promote low-rank solutions through the Hankel matrix representation.Source: Learning with Structure and… · pp. 26–27
• The tension between mixing-time dependence and computational tractability remains open for sparse identification.The cited instantiation reduces to O(dx exp(2s)) separate regressions, which quickly becomes intractable even for moderate sparsity.Source: Learning with Structure and… · p. 26
• When the lag order may reach the horizon, least squares on a state-space conversion is intractable; a LASSO variation may help if the true model has low order.This proposal relies on many of the model's lag coefficients being zero.Source: Learning with Structure and… · p. 27
• Common realizability assumptions exclude bias and misspecification, which can make existing analyses overly optimistic when misspecification interacts with covariate mixing time.A cited worst-case result reports sample complexity deflated by a factor linear in mixing time; the passage notes that additional regularity may avoid this limit.Source: Learning with Structure and… · p. 27

Learning for Nonlinear Identification and Control

• Linear-system learning avoids some nonlinear phenomena, while nonlinear systems can behave differently around different equilibrium points.The supplied discussion identifies this as a distribution-shift issue for learning system behavior.Source: Learning for Nonlinear Identification… · p. 27
• Nonlinear identification offers structural directions beyond sparsity and low rank, including using passivity, dissipativity, or a convex-potential gradient model.The passage presents these as questions and possibilities for future work, not established results.Source: Learning for Nonlinear Identification… · p. 27
• Without useful structure, nonlinear regression can incur a minimax rate that degrades exponentially with state dimension.The example uses a class of k-smooth functions mapping R^dx to [0,1].Source: Learning for Nonlinear Identification… · p. 28

• Anastasios Tsiamis earned his electrical and computer engineering diploma in 2014 and Ph.D. in Electrical and Systems Engineering in 2022.He is a postdoctoral scholar at ETH Zürich, with research interests in statistical learning for control, risk-aware control and optimization, and networked control systems.Source: AUTHOR INFORMATION · p. 28
• Tsiamis was a finalist for the IFAC Young Author Prize and the ACC Best Student Paper Award.Source: AUTHOR INFORMATION · p. 28
• Ingvar Ziemann received his Ph.D. from KTH in 2022 and studied mathematics, economics, and finance.His research focuses on statistical and information-theoretic tools for learning-enabled control and generalization in dynamical systems.Source: AUTHOR INFORMATION · p. 28
• Ziemann received a Swedish Research Council International Postdoc Grant and the IEEE CDC Best Student Paper Award.He also received the Stockholm Mathematics Center Excellent Master Thesis Award.Source: AUTHOR INFORMATION · p. 28