PaperlayerView exact revision on arXiv

Source-linked AI summary

Active Learning for Nonlinear System Identification with Guarantees

Horia Mania, Michael I. Jordan, Benjamin Recht

arXiv:2006.10277v1stat.MLcs.LGmath.OC

TL;DR

Some nonlinear systems with continuous states and inputs require judiciously chosen inputs, while existing identification settings assume informative data or informative i.i.d. inputs. The paper adaptively plans and tracks trajectories for systems with known feature embeddings, achieving a regression-like statistical rate that depends additionally on controllability and planning horizon.

  • Problem

    Existing identification approaches assume the available data are informative or that i.i.d. random inputs produce informative data, although many nonlinear systems require judicious input choices.

    Source: §1 · p. 1

  • Method

    For nonlinear systems with transitions linear in known features, the method plans trajectories toward informative feature directions and tracks them, taking an available informative measurement when possible.

    Source: §1 · p. 1, §3.1 · p. 10, §3.2 · p. 10

  • Results

    The estimation rate is akin to standard supervised linear regression, with additional dependence on system controllability and planning horizon.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Even if trajectory tracking fails, the method is guaranteed to collect at least one informative data point per reference trajectory.

    Source: §1 · p. 3

    The guarantee holds only when the true system lies in model class (1).

    Source: §7 · p. 18

Abstract

from arXiv · show

While the identification of nonlinear dynamical systems is a fundamental building block of model-based reinforcement learning and feedback control, its sample complexity is only understood for systems that either have discrete states and actions or for systems that can be identified from data generated by i.i.d. random inputs. Nonetheless, many interesting dynamical systems have continuous states and actions and can only be identified through a judicious choice of inputs. Motivated by practical settings, we study a class of nonlinear dynamical systems whose state transitions depend linearly on a known feature embedding of state-action pairs. To estimate such systems in finite time identification methods must explore all directions in feature space. We propose an active learning approach that achieves this by repeating three steps: trajectory planning, trajectory tracking, and re-estimation of the system from all available data. We show that our method estimates nonlinear dynamical systems at a parametric rate, similar to the statistical rate of standard linear regression.

1 Introduction

Many nonlinear systems with continuous states and inputs require carefully chosen inputs for identification, beyond settings where random inputs are informative. The paper proposes adaptive data collection for feature-linear nonlinear systems and reports a regression-like estimation rate with additional dependence on controllability and planning horizon.

1 Introduction

  • Prior data-collection approaches may not identify nonlinear systems: some assume the data are informative, while others rely on i.i.d. random inputs being informative.The paper notes that random inputs do not suffice for the described piecewise affine example.Source: §1 · pp. 1–2
  • The approach targets systems with transitions linear in known state-input features, a class that includes linear systems and piecewise affine systems when their piece supports are known.The feature-linear model has also been used to estimate helicopter, Lorenz, and fluid-shedding dynamics.Source: §1 · pp. 1–2
  • The method repeatedly plans a reference trajectory toward a high-uncertainty feature region, tracks it, and re-estimates the system using all collected data.The planner uses past observations and the current estimate; tracking can use that estimate as well.Source: §1 · pp. 2–3
  • The estimate achieves a statistical rate akin to standard supervised linear regression, with additional dependence on system controllability and planning horizon.Even when tracking fails, the method is guaranteed to collect at least one informative data point per reference trajectory.Source: §1 · p. 3

2 Assumptions

The identification guarantees rely on assumptions about feature smoothness and boundedness, process noise, trajectory tracking, controllability, and an initial dataset. These assumptions also constrain the scope of the systems covered.

2 Assumptions

  • The feature map must be Lipschitz and bounded, and smoothness is needed because process noise can otherwise affect subsequent feature vectors arbitrarily.Bounded features support online least-squares analysis, though this condition can be removed for some system classes.Source: §2 · p. 4
  • The chosen system formulation implies bounded states, which can limit applications; an alternative formulation with bounded state increments permits states to grow.The authors retain the bounded-state formulation for simpler exposition.Source: §2 · p. 4
  • Tracking requires inputs that keep error controlled; when γ < 1, the state can approach the reference if process noise is well behaved, while larger γ makes assumptions more stringent.The tracking assumption allows γ ≥ 1, but the guarantee pays a price as γ grows.Source: §2 · pp. 4–5
  • Controllability requires reaching a feature vector aligned with any goal direction within H steps, with alignment at least α; larger H can weaken the guarantee while larger α improves it.The assumptions trade off planning horizon H against controllability parameter α.Source: §2 · p. 5
  • The smoothed piecewise-linear example satisfies the stated assumptions when the input bound is sufficiently large relative to its system parameters and state bound.In that setting, Assumption 3 holds with γ = 0.Source: §2 · p. 6
  • The pendulum example satisfies the controllability assumption, but its Euler discretization is used because a more refined Runge-Kutta discretization does not fit the model form easily.The pendulum’s tracking assumption holds with γ ≥ 1 + h, not γ < 1.Source: §2 · pp. 6–7
  • Process noise is assumed independent, zero-mean, and bounded, with its maximum size constrained by system-dependent controllability, smoothness, and tracking quantities.The text notes that sub-Gaussian noise can replace bounded noise with a truncation argument.Source: §2 · p. 7
  • The method requires an initial trajectory dataset whose ordinary least-squares estimate is sufficiently close to the true dynamics.The required closeness depends on feature-map and tracking quantities.Source: §2 · p. 8

3 Main Result

The paper gives a high-probability estimation guarantee for nonlinear systems under its assumptions, with a rate of the same form as standard linear regression but dependent on controllability and planning horizon. Its active-learning procedure plans toward informative features, tracks those trajectories, and re-estimates from collected data.

3 Main Result

  • The algorithm repeats planning and tracking, then re-estimates the dynamics by ordinary least squares using all observed feature-state transitions.The procedure starts from an initial dataset and outputs its last estimate.Source: §3 · pp. 8–9
  • Theorem 1 gives a high-probability estimation guarantee under Assumptions 1–5 and an initial trajectory satisfying Assumption 6; its rate has the form of linear regression with additional dependence on α and H.The effective sample size is T/H because the method guarantees only one useful measurement per reference trajectory.Source: §3 · pp. 8–9

3.1 Trajectory planning

  • Trajectory planning targets features aligned with the minimum eigenvector of the design matrix, or a high-uncertainty feature when that alignment cannot be reached.The planner’s task is feasible under Assumptions 4 and 6.Source: §3.1 · p. 10

3.2 Trajectory tracking

  • During tracking, the method takes an available input that yields an informative measurement immediately; otherwise it uses feedback to reduce mismatch with the reference trajectory.The tracker stops tracking after taking the immediate informative measurement.Source: §3.2 · pp. 10–11

4 General Guarantee on Estimation

This section gives a general upper bound on the error of ordinary least-squares estimates under stated assumptions. The method repeatedly re-estimates the parameters using the measurements collected so far.

4 General Guarantee on Estimation

  • The section establishes a general upper bound on the error between the OLS estimate and the true parameters.The bound is based on prior analysis by Simchowitz et al..Source: §4 · p. 11
  • At iteration j, the estimate uses the first j observed state-input-transition measurements.The inputs may depend on the observed state history, subject to the stated independence condition on future noise.Source: §4 · p. 11
  • Under Assumptions 5 and 2, with positive minimum-eigenvalue and time-threshold conditions, Proposition 1 gives a guarantee for the OLS estimates.The supplied proposition fragments refer to a universal constant c3 but do not include the full bound.Source: §4 · p. 11

5 Proof of Theorem 1

The proof establishes that planning is feasible, bounds how often the algorithm's informative-measurement condition can fail, and shows that enough feature vectors align with planned directions to obtain the theorem's conclusion.

5 Proof of Theorem 1

  • The trajectory-planning step of Algorithm 1 is always feasible.The proof states this as its first part.Source: §5 · pp. 12–13
  • The proof bounds by N_e the iterations in which the specified informative-measurement conditions occur, using a potential argument.When either condition occurs, the algorithm collects a measurement with a leverage quantity at least β/2.Source: §5 · pp. 12, 14, 15
  • At least T/H − N_e collected measurements have feature vectors aligned by at least α/4 with the minimal eigenvector used to plan reference trajectories.This alignment result supplies the measurements used to establish the design condition.Source: §5 · pp. 12, 16
  • Combining the feature-direction measurements with Proposition 3 establishes the design condition, and Proposition 1 then yields Theorem 1.The proof explicitly identifies (19) as the condition that, together with Proposition 1, gives the theorem.Source: §5 · pp. 12, 16

6 Related Work

Prior finite-time system-identification guarantees largely concern linear systems or nonlinear systems identifiable with non-adaptive inputs. The paper positions its contribution as a first step toward sample-complexity guarantees for nonlinear systems requiring adaptive data collection.

6 Related Work

  • Much of the recent theoretical work gives guarantees for linear systems, including adaptive data collection that maximizes the minimum eigenvalue under input-power constraints [55].Several cited linear-system results assume full state observation, as does this work; partial-observation guarantees are also described [48].Source: §6 · p. 17
  • Prior nonlinear-identification studies largely consider systems identifiable using non-adaptive inputs, including models estimated from i.i.d. inputs [4] [17] [35] [45].The paper describes its work as a first step toward systems requiring adaptive methods.Source: §6 · p. 17
  • Other learning methods use learned dynamics for trajectory planning or exploit control-theoretic priors, but the cited works do not characterize sample complexity [49], [28], [29].Source: §6 · p. 17
  • Related tabular-MDP work studies exploration for policy synthesis and estimation of ergodic Markov chains [25], [56], while another cited result treats a simpler version of model (1).Source: §6 · pp. 17–18

7 Discussion and Open Problems

The paper proposes finite-time estimation through adaptive collection of informative data, while identifying several boundaries of the analysis and open questions for extending it.

7 Discussion and Open Problems

  • Trajectory planning assumes a computational oracle, leaving computationally tractable planning and sample complexity under linearized dynamics open.Source: §7 · p. 18
  • The method relies on full state observations, and statistical understanding under partial observations remains open.Source: §7 · p. 18
  • The guarantee requires the true system to lie in model class (1); finding the best in-class model otherwise remains open.The passage cites Ross and Bagnell [38] as studying this problem under a generative model.Source: §7 · p. 18
  • Only fully actuated systems can satisfy Assumption 3 with γ < 1; extending the result to systems needing multiple steps to recover from disturbances remains open.Source: §7 · p. 18
  • Assumption 4 requires feature vectors to align with any direction; subspace-only alignment prevents full recovery of A⋆, though estimating relevant directions remains an open question.Source: §7 · p. 18
  • The discussion also leaves open whether a statistical theory can be developed for dynamical-system models with infinite-dimensional feature maps φ.Source: §7 · p. 18

A Proof of Proposition 2

The proof analyzes bounded vector updates through determinant and eigenvalue growth. It uses a rank-one update argument to track how informative observations change the matrix sequence.

A Proof of Proposition 2

B Proof of Proposition 3

The proof of Proposition 3 uses directional coverage and eigenvalue updates to establish growth bounds. A standard-basis example identifies a limit on how strong the lower bound can be.

B Proof of Proposition 3

  • The proposition assumes that every unit direction has a vector in V with inner product magnitude at least α, and considers arbitrary vector sequences.Source: B Proof of Proposition 3 · p. 25
  • Cycling through standard basis vectors gives λ_min = T/k when T is a multiple of k, so the proposition's lower bound cannot exceed α²T/k.Source: B Proof of Proposition 3 · p. 25
  • Lemma 2 relates adding vv⊤ to eigenvalue growth when v has a sufficiently large component along the smallest-eigenvalue direction.The lemma bounds the update norm by b and requires |⟨v, u_k⟩| ≥ α.Source: B Proof of Proposition 3 · p. 25

C Refinement of Assumption 6

The refinement chooses a threshold time T⋆ for the stated inequality and updates β in doubling-length epochs. This lets the theorem apply under Assumption 6 with the horizon replaced by T⋆.

C Refinement of Assumption 6

D Detailed pseudo-code of Algorithm 1

The algorithm initializes an ordinary least-squares estimate from the initial trajectory, then repeatedly plans and tracks inputs, updates its data, and re-estimates the system.

D Detailed pseudo-code of Algorithm 1

Loading 2006.10277v1…