PaperlayerView exact revision on arXiv

Source-linked AI summary

Improper Learning for Non-Stochastic Control

Max Simchowitz, Karan Singh, Elad Hazan

arXiv:2001.09254v3cs.LGmath.OCstat.ML

TL;DR

This paper studies non-stochastic control for possibly unknown linear systems with adversarial noise, convex losses, and partial observation. It introduces Disturbance Response Control via Gradient Descent and establishes sublinear regret, including first guarantees for partially observed systems and tight LQG results with unknown systems.

  • Problem

    Non-stochastic control evaluates adaptive controllers by regret against the best hindsight controller because instance-wise optimal control cannot be pre-computed.

  • Method

    The paper introduces Disturbance Response Control via Gradient Descent, using disturbance-feedback iterates and counterfactual costs defined through Markov operators and observations.

  • Results

    The paper gives the first sublinear regret guarantees for partially observed non-stochastic control and the first tight regret bound for LQG with an unknown system.

  • Takeaways & Limitations

    The approach extends non-stochastic control results to partial observation and yields new guarantees for classical stochastic control, including unknown-system LQG.

  • Takeaways & Limitations

    The methods had not yet been implemented or benchmarked against recent online-control methods.

Abstract

from arXiv · show

We consider the problem of controlling a possibly unknown linear dynamical system with adversarial perturbations, adversarially chosen convex loss functions, and partially observed states, known as non-stochastic control. We introduce a controller parametrization based on the denoised observations, and prove that applying online gradient descent to this parametrization yields a new controller which attains sublinear regret vs. a large class of closed-loop policies. In the fully-adversarial setting, our controller attains an optimal regret bound of $\sqrt{T}$-when the system is known, and, when combined with an initial stage of least-squares estimation, $T^{2/3}$ when the system is unknown; both yield the first sublinear regret for the partially observed setting. Our bounds are the first in the non-stochastic control setting that compete with \emph{all} stabilizing linear dynamical controllers, not just state feedback. Moreover, in the presence of semi-adversarial noise containing both stochastic and adversarial components, our controller attains the optimal regret bounds of $\mathrm{poly}(\log T)$ when the system is known, and $\sqrt{T}$ when unknown. To our knowledge, this gives the first end-to-end $\sqrt{T}$ regret for online Linear Quadratic Gaussian controller, and applies in a more general setting with adversarial losses and semi-adversarial noise.

1 Introduction

The paper develops an improper-learning approach to non-stochastic control with partial observations, competing with stabilizing linear dynamical controllers. Its guarantees cover known and unknown systems under adversarial and semi-adversarial regimes, including the first sublinear partial-observation results.

  • Problem: Non-stochastic control replaces stochastic dynamics noise with adversarial perturbations, making regret against the best hindsight controller the performance metric.The learner observes outputs, chooses controls, and incurs adversarially chosen losses.
  • Results: The framework gives the first end-to-end sublinear-regret guarantee for online LQG with an unknown system and the first partial-observation guarantees in the adversarial setting.The contribution applies even when the learner does not know the true system.
  • Approach: Drc-Gd uses a Youla-inspired disturbance-response parametrization based on counterfactual observations and applies online gradient descent to obtain a convex controller.The parametrization represents stabilizing controllers through Nature’s observations and induces losses for online optimization.
  • Results: Known systems obtain sublinear regret under adversarial losses and noise, while strongly convex losses with semi-adversarial noise yield poly log T regret.The known-system adversarial bound is reported as optimal up to logarithmic factors.
  • Comparator class: The method competes with linear dynamical controllers, a class broad enough to encompass H2- and H∞-optimal controllers under partial observation.This extends beyond static state-feedback comparators used in earlier non-stochastic control work.
  • Results: Unknown systems obtain e O(T 2/3) regret in the Lipschitz adversarial regime and e O(T) regret in the strongly convex semi-adversarial regime.The latter result is novel even for full observation and includes the LQG and LQR settings.

2 Assumptions and Regret Benchmark

The paper studies partially observed linear systems and benchmarks algorithms against stabilizing linear dynamical controllers with decaying closed-loop responses. It assumes stable nominal dynamics and bounded, convex, sub-quadratic Lipschitz losses.

  • Assumptions: The main-text analysis assumes a stable nominal system, ρ(A⋆) < 1, while extensions cover stabilizable and detectable potentially unstable systems.The unstable-system treatment uses feedback with a nominal stabilizing controller.
  • Assumptions: Losses are assumed non-negative, convex, sub-quadratic, and Lipschitz on bounded regions, with bounded-noise assumptions throughout.Light-tailed excitations such as Gaussian noise can be handled through truncation with additional logarithmic factors.
  • Controller class: The model includes partially observed linear dynamical systems with controller-internal state, encompassing LQG and H∞ control laws.Linear dynamic controllers are richer than static state-feedback controllers and are needed under partial observation.
  • Regret benchmark: The benchmark class Π(ψ) contains controllers whose induced closed-loop Markov-operator decay is bounded by a proper decay function ψ.The decay function measures the response to past inputs and is invariant to the state-space representation.
  • Regret benchmark: Regret compares the algorithm’s accumulated loss with the best hindsight controller in Π(ψ), chosen with complete knowledge of perturbations and losses.The benchmark can be extended to controllers with fixed or bounded-period affine terms.

3 Disturbance Response Control

The paper replaces disturbance feedback with a convex controller parametrization based on counterfactual, denoised observations called Nature’s y’s. This parametrization can approximate the behavior of stabilizing linear dynamical controllers under partial observation.

  • Motivation: Under partial observation, the actual disturbances cannot generally be recovered, motivating a controller representation based on observations instead.Recovery can fail when C⋆ does not possess a left inverse.
  • Nature’s y’s: Nature’s y’s are the outputs that would result from the same disturbances if zero control were applied, and they do not depend on the chosen controls.For a fixed known system, the observed output sequence is completely determined by Nature’s y’s and the control inputs.
  • Nature’s y’s: Nature’s y’s can be computed exactly from control inputs and corresponding system outputs, even when the disturbances themselves are unknown.This observation enables execution of the controller parametrization using denoised observations.
  • Disturbance Response Control: Disturbance Response Control uses a finite sequence of matrices M to form a convex parametrization of controllers through their actions on Nature’s y’s.The parametrization is based on the classical Youla formulation and is designed to accommodate partial observation.
  • Approximation guarantee: For any controller in Π(ψ), a length-m DRC approximates its behavior, with fidelity governed by the nominal system response and comparator decay.When ψ(m) decays exponentially, the approximation error decreases correspondingly and does not depend on the comparator’s state dimension.

4 Algorithmic Description & Main Result

The algorithm reduces control to online convex optimization with memory by defining counterfactual costs for recent DRC decisions. It then applies online gradient descent, using least-squares system estimation when the dynamics are unknown.

  • OCO with Memory: The analysis reduces control to online convex optimization with memory, where each loss depends on the current and previous h decisions.Policy regret compares these memory-dependent losses with the best fixed decision in hindsight.
  • Counterfactual costs: Counterfactual costs evaluate the loss that would have occurred if a non-stationary sequence of DRC parameters had been used during the previous h steps.These costs are defined using Markov operators and Nature’s y’s rather than an explicit system-parameter realization.
  • Online optimization: The algorithm specializes the memory-dependent costs to unary functions and runs online gradient descent on the resulting DRC losses.Unary notation uses parentheses for a single M and brackets for a sequence of recent parameters.
  • Unknown dynamics: When the system is unknown, the procedure first estimates G⋆ by least squares for N steps and then runs online gradient descent with the estimate.The stated algorithms target stable systems; unstable systems can incorporate a nominal stabilizing controller.
  • Algorithm: The implementation initializes a DRC parameter, selects control inputs, observes each loss, and updates the disturbance-feedback controller.The feasible parameter set constrains the matrix sequence by length m and an ℓ1 operator-norm radius.

9 end

The paper specifies assumptions, algorithms, and main regret guarantees for known and unknown partially observed systems, including non-stochastic, semi-adversarial, LQR, and LQG settings.

  • Assumptions and setup: The framework assumes finite horizons, known decay parameters, and decay bounds that are typically geometric.Under Assumption 4, both the true system and comparator responses decay as Cρ^n.
  • Algorithms: The unknown-system procedure first estimates Markov parameters by least squares, then runs gradient descent with the estimated operators.The estimation stage uses N exploratory Gaussian inputs before regret minimization begins.
  • Main guarantees: Known systems achieve the main non-stochastic-control regret theorem, with a poly(log T) specialization under typical decay and noise bounds.The theorem uses exact Markov parameters and a finite-memory controller parametrization.
  • Main guarantees: Unknown systems achieve a separate high-probability regret guarantee after an estimation stage whose prescribed length scales as N = (Th^2R_MR_natC_δ)^(2/3).The guarantee is stated with probability 1 − δ − T^−Ω(log^2 T).
  • Fast-rate regime: The fast-rate results require smooth, strongly convex losses and semi-adversarial noise combining adversarial disturbances with stochastic persistent excitation.The framework also specializes to LQR and LQG, including known and unknown systems.
  • LQR and LQG: The LQR specialization uses fully observed quadratic losses, while the LQG specialization uses quadratic output-control losses and a latent-state estimate.For LQG, the controller is represented as an LDC induced by the estimated-state dynamics.

5 Analysis for Known System

The known-system analysis decomposes regret into burn-in, truncation, policy, and approximation terms, then controls policy regret through online convex optimization with memory.

  • Regret decomposition: The analysis decomposes regret into burn-in loss, algorithm truncation error, comparator truncation error, policy regret, and policy approximation error.The dominant term is identified as the f-policy regret, while truncation terms measure finite-history discrepancies.
  • Magnitude control: The controller’s input magnitudes and loss Lipschitz constants are controlled uniformly to make the decomposition applicable.These bounds rely on the loss-growth assumptions and bounded controller responses.
  • Conclusion: Summing the truncation, policy, and approximation bounds yields the known-system regret guarantee.The proof combines Lemmas 5.2, 5.3, and 5.5 with the controller-approximation theorem.
  • Policy regret: Online gradient descent on unary losses supplies the policy-regret bound through an OCO-with-memory reduction.The reduction uses Lipschitzness, the feasible-set diameter, and a learning rate depending on d_min, L, h, and R_M.
  • Controller approximation: The disturbance-response parametrization is connected to linear dynamical controllers through a control approximation identity.The construction maps controller realizations into finite-memory matrices whose induced behavior approximates the target closed-loop dynamics.

6 Analysis for Unknown System

The unknown-system analysis establishes estimation stability, bounds estimation and approximation errors, and reduces the remaining policy regret to the known-system analysis.

  • Estimation: The unknown-system procedure estimates the hidden system under an explicit estimation condition and a high-probability guarantee.The analysis assumes sufficient knowledge of the system-response decay and uses Algorithm 2’s estimation event.
  • Estimation stability: A sufficiently accurate system estimate prevents history-dependent denoised observations from creating unstable feedback.Lemma 6.1 gives bounds on the estimated natural-output sequence under the estimation condition.
  • Regret decomposition: Unknown-system regret includes an initial estimation-and-burn-in term, loss approximation error, policy regret, and comparator approximation error.The approximation terms measure discrepancies caused by replacing the true system and natural observations with their estimates.
  • Policy regret: The unknown-system policy regret is reduced to the known-system policy-regret bound under the estimation condition.The policy approximation error remains the same as in the known-system analysis.
  • Final guarantee: Choosing the estimation length N balances estimation, burn-in, and approximation contributions in the proof of the unknown-system theorem.The theorem proof combines the estimation bound with the policy and approximation lemmas and selects N at the stated scale.
  • Approximation errors: The estimated natural outputs become accurate after the exploration stage, and the resulting approximation error decreases with system-estimation accuracy.The analysis separately bounds loss approximation and comparator approximation errors.

7 Logarithmic Regret for Known System

The section establishes logarithmic regret for known systems under semi-adversarial noise by combining conditional strong convexity with online gradient descent and a memory-aware analysis.

  • Conditional strong convexity: The induced losses are α_f-strongly convex after conditioning on sufficiently past observations.Proposition 7.1 supplies the strong-convexity property used in the proof of Theorem 4.
  • Conditional strong convexity: Logarithmic regret follows when conditional expected losses are strongly convex, even though individual losses are not necessarily strongly convex.The analysis uses conditional functions and with-memory regularity conditions to obtain this guarantee.
  • Gradient descent with memory: The proof applies gradient descent with memory under Lipschitz, smoothness, and conditional strong-convexity conditions.Theorem 7 provides the generic regret bound, which is specialized to the control problem.
  • Robustness to errors: Strongly convex online gradient descent has logarithmic regret and quadratic sensitivity to gradient errors, allowing system-estimation errors to contribute as Tϵ_G^2/α.This robustness is central to the unknown-system analysis and motivates the true-prediction construction.
  • Regret decomposition: The regret decomposition separates burn-in, truncation, policy-approximation, and control-approximation terms, with the latter two coupled through a shared comparator.This decomposition supports the reduction from controller regret to online convex optimization with memory.

9 Concluding Remarks

The paper presents DRC-GD as an adaptive controller for partially observed systems and reports first sublinear regret guarantees in several adversarial and semi-adversarial settings. It also identifies implementation, benchmarking, and parameter-selection extensions for future work.

  • Main conclusions: DRC-GD provides the first sublinear regret guarantees for partially observed systems with known or unknown dynamics under adversarial noise.The controller is inspired by Youla parametrization and uses an improper convex controller class.
  • Main conclusions: The reported guarantees include optimal rates for partially observed non-stochastic control and the first bound for classical LQG extended to semi-adversarial settings.The conclusion highlights both the non-stochastic and LQG consequences.
  • Future work: Future work includes implementation, benchmarking against online-control and stochastic-control methods, adaptive parameter selection, and extensions to mispecification, safety, and distributed control.The authors specifically note removing the need for prior knowledge of system properties as a goal.

A.4 Relationship Between Parameters (Assumption 4)

This section relates system and noise parameters used in the regret analysis and situates the guarantees against prior work. It explains how noise bounds and stability yield geometric decay while noting assumptions and comparison regimes.

  • Parameter relationships: SubGaussian perturbations imply a high-probability bound on transformed noise involving σ, dimension, and log(T/δ).This yields R_nat ≤ R_G⋆σd log(T/δ) for d = max{d_u,d_y}.
  • Parameter relationships: Stable system matrices produce geometrically decaying impulse-response terms through a Lyapunov inequality.The decay is summarized by a bound proportional to κ(1−ϵ)^(n−1)/ϵ.
  • Parameter relationships: The analysis can tolerate constant-factor parameter misspecification, but truncation horizons must remain conservative enough to make decay terms at most about 1/T.Strongly convex settings also require using an effective strong-convexity parameter below the true modulus.
  • Comparison with prior work: The comparison tables distinguish known and unknown systems and separate non-stochastic from stochastic or semi-adversarial noise regimes.The paper compares against stabilizing linear dynamical controllers, which strictly generalize state feedback.
  • Comparison with prior work: For stochastic linear control with fixed quadratic costs, state feedback is optimal up to additive terms that do not grow with T.This qualification contrasts the broader comparator class used in the non-stochastic results.

B.2 Regret Lower Bounds for Known Systems

The section establishes lower-bound and stabilized-system results relevant to competing with broad linear dynamical controller classes. It also explains how approximate observer feedback avoids the exact system knowledge required by classical Youla parametrization.

  • √T regret is necessary to compete with the optimal state-feedback controller in specified fully observed stochastic or deterministic-noise regimes.
  • The lower-bound construction uses a two-dimensional system, scalar control, state-feedback policies, and a family of Lipschitz-loss or i.i.d.-noise settings.
  • Ω(T^1/2) pseudo-regret follows from choosing Bernoulli noise parameters separated by ϵ = Ω(T^-1/2) and applying a hypothesis-testing argument.
  • The lower-bound analysis also applies when disturbances are moved into losses that may depend on the current state and prior state-action history.
  • Stabilized systems: For unstable systems, the framework assumes stabilizability and detectability and uses LDC-Ex with exact observer feedback to recover classical Youla parametrization.
  • Stabilized systems: Exact Youla parametrization requires full system knowledge, whereas approximate observer feedback combines Youla structure with Nature’s η’s to remain convex under inexact knowledge.

C.5 Expressivity of Drc-Ex

This section shows that Drc-Ex conversion operators preserve stable-system structure across nominal and target controllers. Consequently, the parametrization can approximate stabilizing linear dynamical controllers, including inexact observer-feedback settings.

  • A π0 → π conversion operator maps exogenous-input behavior under a nominal controller to the input-output behavior of a target policy.
  • Theorem 10 represents conversion operators through stable Markov operators or their convolutions across internally stable, static-feedback, internally stable-feedback, and observer-feedback cases.
  • Geometric decay follows for the conversion operators when the relevant nominal, closed-loop, or observer-feedback systems are stable.
  • Approximate observer feedback: Inexact observer feedback yields a conversion operator formed by convolving three stable-system Markov operators under the stated spectral-radius conditions.
  • The conversion-operator class has the same expressive power as the stable-system case because convolutions of geometrically decaying operators retain geometric decay.
  • Stabilized systems: The Drc-Ex construction extends the framework to arbitrary stabilizable and detectable systems while requiring access to a stabilizing nominal controller.

D.2 Estimation Bounds: Proof of Theorems 6 & 6b

This section develops estimation guarantees for the system-response operators used by the stabilized algorithm. It combines concentration, self-normalized martingale, covering, and magnitude arguments to control estimation and approximation errors.

  • The estimation analysis targets both G_ex→η and G_ex→(y,u), with Algorithm 2 recovered as a special case for the latter operator.
  • Theorem 6b provides high-probability bounds for Algorithm 5 when the horizon, input dimension, confidence, and decay conditions satisfy the stated assumptions.
  • High-probability operator estimates use Gaussian concentration, self-normalized martingale bounds, and a covering argument over the unit sphere and response lags.
  • The proof controls truncation error using decay of the system-response operators and controls finite-horizon estimation error through bounds on the operator-norm deviation matrix.
  • Stabilized setting: Under the stabilized estimation condition, estimated operators and algorithmic controls remain bounded by quantities depending on nominal-system and response-operator magnitudes.
  • Stabilized setting: The stabilized regret proof preserves the same bound up to constants after accounting for estimated responses, control magnitudes, loss approximation, and comparator approximation errors.

E Strongly Convex, Semi-Adversarial Regret

This section extends semi-adversarial regret guarantees to stabilized systems by establishing strong convexity for the induced prediction losses. The resulting rates depend polynomially on a system-dependent exponent, which is zero in important special cases.

  • Strong convexity: Strong convexity of the prediction losses decays at most polynomially with the history length m.For general stabilized controllers, the exponent and threshold may depend on system parameters.
  • Special cases: Static-feedback stabilization gives psys = 0, recovering the internally stable special case with explicit bounds on αsys.For general stabilized systems, psys may remain positive, while it is zero in many settings of interest.
  • Known systems: The stabilized known-system regret is bounded by a polylogarithmic term whose exponent depends on psys.The polynomial factors do not otherwise depend on system parameters.
  • Unknown systems: Theorem 5 similarly extends the unknown-system fast-rate guarantee, with an additional system-dependent term involving the dimension d3.The rate inherits the same psys dependence as the known-system result.

F.2 Internally Stabilized Strong Convexity and Proof of Proposition 7.1b

This section proves polynomial lower bounds on strong convexity for internally stabilized systems using Z-transform functionals. It also gives transparent special-case bounds for static feedback and identifies conditions ensuring a positive limiting strong-convexity parameter.

  • Z-transform characterization: The strong-convexity parameter is controlled by H-functionals of the excitation-to-output and noise transfer operators.For sufficiently large h and k, the parameter is lower bounded by products of these functionals.
  • General controllers: For general controllers, Hmin[Gex→(y,u)] can vanish, but spectral separation of A⋆ from the unit circle yields Hmin[Gex→(y,u)] > 0.This condition produces a positive α∞ through the strong-convexity characterization.
  • Polynomial lower bound: The H[h]-functional decays at most polynomially with h, yielding αm,h ≥ αsys m^psys for suitable system-dependent constants.Stability supplies geometric decay conditions needed to choose a sufficiently large system-dependent threshold msys.
  • Static feedback: For static feedback stabilization, Proposition F.2 provides transparent lower bounds on the limiting strong-convexity parameter α∞.The setting includes full observation and some partially observed systems stabilized by an appropriate feedback matrix.
  • Static feedback: Positive state noise can ensure α∞ > 0 without the approximate-diagonalizability assumptions used in earlier bounds.With C⋆ = I, the result recovers prior bounds even with stabilizing feedback.

F.3 Proof of Theorem 11

This section proves Theorem 11 by expressing strong convexity through finite Toeplitz operators and lower bounding their smallest singular values with H-functionals. The result transfers these operator bounds to conditional prediction losses.

  • Toeplitz representation: The proof first represents the strong-convexity parameter using a Toeplitz operator constructed from the relevant Markov operator.The operator encodes finite impulse-response blocks of the system dynamics.
  • Toeplitz lower bound: The smallest singular value of the Toeplitz operator is lower bounded by an H[h]-functional of the underlying Markov operator.The proof uses finite-horizon signal truncation and Z-transform arguments.
  • Strong convexity: The resulting conditional losses are αloss · αm,h,k-strongly convex, and also αloss · α∞-strongly convex when the limiting bound applies.The conditional expectation preserves strong convexity through the covariance lower bound.
  • Noise contribution: The proof factors the finite-horizon covariance through the noise-transfer Markov operator and its block Toeplitz representation.Transpose and block-diagonal covariance identities connect the noise process to the Toeplitz singular-value bound.
  • Analytic lower bound: The H[h]-functional lower bound follows by combining rational-signal norm bounds with analytic-function control of transfer-function singular values.These steps yield polynomial degradation in h rather than arbitrary collapse.

F.4 Proof of Proposition 7.1 (Strong Convexity for the Stable Case)

This section proves strong convexity directly for stable systems, avoiding the Z-transform conditions required for stabilized systems. It also derives the analytic and signal-norm ingredients used for general transfer operators.

  • Stable-system argument: For stable systems, strong convexity can be lower bounded directly without conditions on the decay functions ΨGex→(y,u) and ΨGnoise.The direct argument avoids passing through the Z-transform framework.
  • Excitation contribution: A Toeplitz operator for the excitation-to-output map contains an identity submatrix, giving a smallest-singular-value lower bound of 1.This follows by repartitioning the operator in the stable case.
  • Noise contribution: The noise contribution is lower bounded using a diagonal covariance structure and a corresponding block Toeplitz submatrix.Together with the excitation bound, this establishes the stable-case strong-convexity result.
  • Signal norms: Finite-support signals in Wh have unit H2 norm and bounded H∞ norm, preventing their frequency responses from becoming arbitrarily concentrated.This yields a frequency set of measure proportional to 1/(h + 1) on which the signal remains sufficiently large.
  • Analytic argument: For transfer operators with σdin(D) > 0, the minimum singular value of the Z-transform vanishes at only finitely many frequencies.Analyticity then supplies a polynomial lower bound for the H[h]-functional.

G.3.2 Proof of Lemma G.3

The proof normalizes a conditionally centered, bounded process and uses blocking to recover martingale structure. A concentration lemma and standard decomposition then establish the desired bound.

  • Normalization: The proof rescales Z_t by U_t := 4L_f∥z_t − z⋆∥_2, obtaining a bounded normalized process with conditional mean zero.The normalization ensures |Z̄_t| ≤ 1 almost surely while preserving conditional centering.
  • Blocking: Because Z̄_t is centered conditional on F_{t−k}, rather than F_{t−1}, the proof uses a blocking argument across k residue classes.The blocked indices are defined as t_{i,j} = k + i + jk − 1.
  • Martingale concentration: Within each block, the terms form martingale sequences with respect to the induced filtration, and the normalized increments are 1/4-sub-Gaussian.This enables application of a concentration result for adapted processes with conditionally sub-Gaussian terms.
  • Concentration bound: Lemma G.6 is applied with X_j = Z̄_{t_{i,j}} and Y_j = U_{t_{i,j}} to control the resulting weighted sums.The lemma assumes adaptedness and conditional sub-Gaussianity for the paired processes.
  • Conclusion: The proof combines a direct bound from Theorem 12 with a separate bound on the second term, thereby establishing the desired result.The final decomposition follows the argument attributed to Anava et al. (2015).
Loading 2001.09254v3…