title: Certainty Equivalent Perception-Based Control
authors: Sarah Dean Benjamin Recht
text: 
  
  Controlling Level of Unconsciousness by Titrating Propofol with Deep Reinforcement Learning
      Gabriel Schamberg^⋆1,2 
  Marcus Badgeley^⋆2,3
  Emery N. Brown1,2,3
      December 30, 2023
  ===========================================================================================
  
  
  
  
  In order to certify performance and safety, feedback control requires precise characterization of sensor errors.
  In this paper, we provide guarantees on such feedback systems when sensors are characterized by solving a supervised learning problem.
  We show a uniform error bound on nonparametric kernel regression under a dynamically-achievable dense sampling scheme.
  This allows for a finite-time convergence rate on the sub-optimality of using the regressor in closed-loop for waypoint tracking.
  We demonstrate our results in simulation with simplified unmanned aerial vehicle and autonomous driving examples.
  
  
  
  
  
  
  
  § INTRODUCTION
  
  Machine learning provides a promising avenue for incorporating rich sensing modalities into autonomous systems.
  However, our coarse understanding of how ML systems fail limits the adoption of data-driven techniques in real-world applications.
  In particular, applications involving feedback require that errors do not accumulate and lead to instability.
  In this work, we propose and analyze a baseline method for incorporating a learning-enabled component into closed-loop control, providing bounds on the sample complexity of a reference tracking problem.
  
  
  Much recent work on developing guarantees for learning and control has focused on the case that dynamics are unknown <cit.>.
  In this work, we consider a setting in which the uncertainty comes from the sensor generating observations about system state.
  By considering unmodeled, nonlinear, and  potentially high dimensional  sensors, we capture phenomena relevant to modern autonomous systems <cit.>.
  
  
  Our analysis combines contemporary techniques from statistical learning theory and robust control. 
  We consider learning an inverse perception map with noisy measurements as supervision, and show that it is necessary to quantify the uncertainty pointwise to guarantee robustness.
  Such pointwise guarantees are more onerous than  typical mean-error generalization bounds, and require a number of samples scaling exponentially with dimension.
  However, many interesting problems in robotics and automation are low dimensional, and we provide a high-probability pointwise error bound on nonparametric regression for such scenarios. 
  Under a dynamically feasible dense sampling scheme, we show uniform converge for the learned map.
  Finally, we analyze the suboptimality of using the learned component in closed-loop, and demonstrate the utility of our method for reference tracking.
  We close with several numerical examples showing that our method is feasible for many problems of interest in autonomy.
  Full proofs of the main results, further discussion on controller synthesis, illustrative examples, and experimental details are included in the longer version of this paper <cit.>.
  
  
  
  
  
   §.§ Problem Setting
  
  
  Motivated by situations in which control is difficult due to sensing, we consider the task of  waypoint tracking for a system with known, linear dynamics and complex, nonlinear observations.
  The setting is succinctly described by the motivating optimal control problem:
  
      min_π     
      sup_{x^_k}∈
      x_0_∞≤σ_0[ Q^1/2(x_k-x^_k);        R^1/2u_k ]_∞
            x_k+1 = Ax_k + Bu_k ,   z_k = g(C x_k),   u_k = π(z_0:k, x^_0:k),
  
  where x∈^n is the system state, u∈^m is the control input, 
  
  z∈^q is the system observation, and we use the shorthand x_0:k = (x_0, …, x_k). The linear dynamics are specified by A∈^n× n, B∈^n× m, and the matrix C∈^p× n determines the state subspace that affects the observation, which we will refer to as the measurement subspace. 
  We assume that (A,B) is controllable and (A,C) is observable.
  This optimal control problem seeks a causal policy π to minimize a robust waypoint tracking cost. 
  The objective in (<ref>) penalizes the maximum deviation from any reference trajectory in the class  as well as the maximum control input, with the relative importance of these terms determined by Q∈^n× n and R∈^m× m.
  A common class of reference signal is those with bounded differences, i.e. x_k^ - x_k+1^_∞≤Δ.
  
  As defined by the constraints of this problem, the system has linear dynamics, but nonlinear observations (<ref>).
  We suppose that the parameters of the linear dynamics (A,B,C) are known, while the observation function g:^p→^q is unknown.
  This emulates a natural setting in which the dynamics of a system are well-specified from physical principles (e.g. vehicle dynamics), while observations from the system (e.g. camera images) are complex but encode a subset of the state (e.g. position).
  We assume that g is continuous and that there is a continuous inverse function h:^q→^p with h(g(y)) = y.
  
  
  
  For the example of a dashboard mounted camera, such an inverse exists whenever each camera pose corresponds to a unique image, which is a reasonable assumption in sufficiently feature rich environments.
  
  
  
  
  If the inverse function h were known, then the optimal control problem is equivalent to a linear output-feedback control
  problem. 
  We expand further on this point in Section <ref>.
  
  We therefore pose a learning problem focused on the unknown inverse function h, which we will call a perception map.
  We suppose that during the training phase, there is an additional system output, 
  
      y_k^ = Cx_k + η_k
  
  where each η_k is zero mean and has independent entries bounded by σ_η.
  This assumption corresponds to using a simple but noisy sensor for characterizing the complex sensor.
  The noisy system output will both supervise the learning problem and allow for the execution of a sampling scheme where the system is driven to sample particular parts of the state space.
  Notice that due to its noisiness, using this sensor for waypoint tracking would be suboptimal compared using transformed observations. 
  
  We will show that the certainty equivalent controller, i.e. the controller which treats the approximation h(z) ≈ Cx as true, achieves a cost which converges towards optimality.
  
  [Informal]
  Certainty equivalent control using a perception map learned with T sampled data points by our method achieves a suboptimality bounded by
  
      c(π) - c(π_⋆)≲ L r_⋆ S_⋆( σ/T)^1/p+4 .
  
  Here, c(·) is the cost objective in (<ref>), L describes the continuity of the relationship between system state and the observations, r_⋆ bounds the region of system operation under the optimal control law, S_⋆ is the sensitivity to measurement error of the optimal closed-loop, σ is proportional to the sensor noise in (<ref>), and p is the dimension of measurement subspace.
  
  
   
  
  
   §.§ Related Work
  
  
  The model we study is inspired by examples of control from pixels, primarily in the domain of robotics.
  At one end of the spectrum, calibrated camera characteristics are incorporated directly into physical models; this type of visual-inertial odometry enables agressive control maneuvers <cit.>.
  On the other end are policies that map pixels directly to low-level control inputs, for example via imitation learning <cit.>.
  Our model falls between these two approaches: relying on known system dynamics, but deferring sensor characterization to data.
  
  
  The observation of a linear system through a static nonlinearity is classically studied as a Weiner system model <cit.>.
  While there are identification results for Weiner systems,
  they apply only to single-input-single-output systems, and often require
  
  assumptions that do not apply to the motivation of cameras <cit.>.
  More flexible identification schemes have been proposed <cit.>, but
  they lack theoretical guarantees.
  Furthermore, these approaches focus on identifying the full forward model, which may not be necessary for good closed-loop performance.
  The variant of Weiner systems that we study is closely related to
  
  our recent work, which focused on robustness in control design
   <cit.>.
  We now extend these ideas to directly consider issues of sampling and noise.
  
  
  
  
  
  
  
  
  There is much related and recent work at the intersection of learning and control.
  Similar in spirit is a line of work on the Linear Quadratic Regulator which focuses on issues of system identification and sub-optimality <cit.>.
  This style of sample complexity analysis has allowed for illuminating comparisons between model-based and model-free policy learning approaches <cit.>.
  <cit.> show that the simple strategy of model-based certainty equivalent control is efficient, though the argument is specialized to linear dynamics and quadratic cost.
  For nonlinear systems, analyses of learning often focus on ensuring safety over identification or sub-optimality <cit.>, and rely on underlying smoothness for their guarantees <cit.>.
  An exception is a recent result by <cit.>
  
  which presents finite sample guarantees for parametric nonlinear system identification.
  
  
  While the majority of work on learning for control focuses on settings with full state observation, output feedback is receiving growing attention for linear systems <cit.> and for safety-critical systems <cit.>. Recent work in closely related problem settings includes <cit.>, who develop sample complexity guarantees for LQR with nonlinear observations and <cit.>, who leverage representation learning in Block MDPs; however, neither address issues of stability due to focusing on finite horizon problems.
  
  
  The statistical analysis presented here focuses on nonparametric pointwise error bounds over a compact set.
  Distinct from mean-error generalization arguments most common in learning theory,
  our analysis is directly related to classical statistical results on uniform convergence <cit.>.
  Our motivation is related to conformal regression <cit.>, which relies on exchangeability assumptions that can be adapted to data from dynamical systems with mixing arguments <cit.>.
  
  
  
  
  
  
    
  
  
  
  
  § UNIFORM CONVERGENCE OF PERCEPTION
  
  
  In this section, we introduce a sampling scheme and nonparametric regression strategy for learning the predictor h and show that the resulting errors are uniformly bounded.
  While it is typical in the machine learning community to consider mean-error generalization bounds,
  we show in the following example that it is necessary to quantify the uncertainty pointwise to guarantee robustness.
  This motivating example shows how errors within sets of vanishingly small measure can cause systems to exit bounded regions of well-characterized perception and lead to instability.
  For a simple setting, we construct a reference trajectory that leads to instability, illustrating that feedback control objectives require very strong function approximation error bounds.
  
  
  Consider a one-dimensional linear system that is open-loop unstable (|a|>1) with
  an arbitrary linear reference tracking controller: 
  
  
  
      x_k+1 = a x_k + u_k,   
      u_k = ∑_t=0^k K_t^ x^_k-t +K_t^x x_k-t .
  
  Further suppose that the perception map has been characterized within the bounded interval [-r,r] and is imperfect only around the point x̅∈[-r,r]:
  
      x = h(g(x)) =  0    |x|≥ r  or   x=x̅
      
      x   otherwise
  
  
      x = h(g(x)) =  0   if   |x|≥ r  or   x=x̅  and   x  otherwise.
  
  Then consider a trajectory starting at x_0=0 with x^_0 = x̅/K_0^r, x^_1 = 1/K_0^r(r-(a+K_1^rK_0^r)x̅), and
  
  x^_k=0 for all k≥ 2.
  Despite an initial condition and reference trajectory contained within the well-characterized interval, the perception error at x̅ causes  the unstable system 
  
  trajectory
  
      |x_k| = |a^k-1x̅| →∞ as k→∞ .
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Motivated by this example, we begin by introducing a method for nonparametric regression and present a data-dependent pointwise error bound.
  Then, we propose a dense sampling scheme and show a uniform error bound over the sampled region of the measurement subspace.
  
  While it is typical in the machine learning community to consider mean-error generalization bounds, robust control objectives require that uncertainty be quantified pointwise to guarantee.
  It is easy to construct examples in which 
  
  errors within sets of vanishingly small measure cause systems to exit bounded regions of well-characterized perception and lead to instability (e.g. <cit.>).
  
  
  Therefore, we begin by introducing a method for nonparametric regression and present a data-dependent pointwise error bound.
  Then, we propose a dense sampling scheme and show a uniform error bound over the sampled region of the measurement subspace.
  
  
  
  
   §.§ Nonparametric Regression
  
  
  Since uniform error bounds are necessary for robust guarantees, we now introduce a method to learn perception maps with such bounds.
  For simplicity of analysis and exposition, we focus on Nadarya-Watson estimators.
  We expect that our insights will generalize to more complex techniques,
  and we demonstrate similarities with additional regressors in simulation experiments presented in Section <ref>.
  
  The Nadarya-Watson regression estimators with training data {(z_t, y_t^)}_t=0^T, bandwidth γ∈_+, and metric ρ:^q×^q→_+ have the form
  
      h(z) = ∑_t=0^T _γ(z_t,z)/s_T(z) y^_t ,   s_T(z) = ∑_t=0^T _γ(z_t,z),  _γ(z_t,z) = (ρ(z_t,z)γ)  ,
  
  with h (z) = 0 when s_T(z)=0 and :_+→[0,1] is a kernel function.
  We assume that the kernel function is Lipschitz with parameter L_ and that (u)=0 for u>1, and define the quantity
  V_ = ∫_^p_+(y_∞) d y. 
  Thus, predictions are made by computing a weighted average over the labels y_t^ of training datapoints whose corresponding observations z_t are close to the current observation, as measured by the metric ρ.
  We assume the functions g and h are Lipschitz continuous with respect to ρ, i.e. for some L_g and L_h
  
      ρ(g(y), g(y')) ≤ L_g y-y'_∞,  h(z) - h(z')_∞≤ L_hρ(z, z') .
  
  
  
  While our final sub-optimality results depend on L_g and L_h, the perception map and synthesized controller do not need direct knowledge of these parameters.
  
  
  For an arbitrary z with s_T(z)≠ 0, the prediction error can be decomposed as
  
      h(z) - h(z)_∞   ≤∑_t=0^T κ_γ(z_t,z)/s_T(z)(Cx_t - Cx) _∞ + ∑_t=0^T κ_γ(z_t,z)/s_T(z)η_t _∞ .
  
  The first term is the approximation error due to finite sampling, even in the absence of noisy labels.
  This term can be bounded using the continuity of the true perception map h.
  The second term is the error due to measurement noise.
  We use this decomposition to state a pointwise error bound, which can be used to provide tight data-dependent estimates on error.
  
  
  For a learned perception map of the form (<ref>) with training data as in (<ref>) collected during closed-loop operation of a system satisfying (<ref>), we have with probability at least 1-δ that for a fixed z with s_T(z)≠ 0,
  
      h(z) - h(z)_∞   ≤γ L_h +  σ_η/√(s_T(z))√(log(p^2√(s_T(z))/δ)) .
  
  
  
  We present the proof of this result in the Appendix <ref>.
  
  The expression illustrates that there is a tension between having a small bandwidth γ and ensuring that the coverage term s_T(z) is large.
  Notice that most of the quantities in this upper bound can be readily computed from the training data; only L_h, which quantifies the continuity of the map from observation to state, is difficult to measure.
  We remark that while useful for building intuition, the result in Lemma <ref> is only directly applicable for bounding error at a finite number of points. 
  Since our main results handle stability over infinite horizons, they rely on a modified bound introduced in Appendix <ref> which is closely tied to continuity properties of the estimated perception map h and the sampling scheme we propose in the next section.
  Since our main results handle stability over infinite horizons, they rely on a modified bound introduced in the full version of this paper <cit.> which is closely tied to continuity properties of the estimated perception map h and the sampling scheme we propose in the next section.
  
  
  
  
  
   §.§ Dense Sampling
  
  
  We now propose a method for collecting training data and show a uniform, sample-independent bound on perception errors under the proposed scheme.
  This strategy relies on the structure imposed by the continuous and bijective map g, which ensures that driving the system along a dense trajectory in the measurement subspace corresponds to collecting dense samples from the space of observations.
  In what follows, we provide a method for driving the system along such a trajectory.
  
  
  We assume that during training, the system state can be reset according to a distribution 𝒟_0 which has has support bounded by σ_0. 
  We do not assume that these states are observed. 
  Between resets, an affine control law drives the system to evenly sample the measurement subspace with a combination of a stabilizing output feedback controller and reference tracking inputs:
  
      u_t = ∑_k=0^t K_k y_t-k^ + u_t^ .
  
  
  The stabilizing feedback controller prevents the accumulation of errors resulting from the unobserved reset state.
  The closed-loop trajectories resulting from this controller are
  
      x_t = Φ_x(t)x_0 + ∑_k=1^tΦ_xu(k) u^_t-k+ Φ_xn(k)  η_t-k ,
  
  where the system response variables {Φ_x(k), Φ_xu(k), Φ_xn(k)}_k≥ 0 arise from the interaction of the stabilizing control law with the linear dynamics; we revisit this fact in detail in Section <ref>.
  As long as the feedback control law {K_k}_k≥ 0 is chosen such that the closed-loop system is stable, the system response variables decay.
  Designing such a stabilizing controller is possible since (A,B) is controllable and (A,C) is observable.
  We therefore assume that for all k≥ 0
  
      max{CΦ_x(k)_∞, CΦ_xn(k)_∞}≤ Mρ^k,
  
  for some M≥ 1 and 0≤ρ<1.
  
  
  
  
  
  The reference inputs u_t^ are chosen to ensure even sampling.
  
  Since the pair (A, B) is controllable, these reference inputs can drive the system to any state within n steps.
  Algorithm <ref> leverages this fact to construct control sequences which drive the system to points uniformly sampled from the measurement subspace.
  Its use of system resets ensures independent samples; we note that since the closed-loop system is stable, such a “reset” can approximately be achieved by waiting long enough with zero control input.
  
  As a result of the unobserved reset states and the noisy sensor, the states visited while executing
  Algorithm <ref> do not exactly follow the desired uniform distribution. They can be decomposed into two terms:
  
      C x_n,ℓ = ∑_k=1^n C Φ_xu(k) u^_n-k, ℓ + (C Φ_x(n)x_0,t + ∑_k=1^n C Φ_xn(k) η_n-k, ℓ) =: y_ℓ^+w_ℓ
  
  where y^_ℓ is uniformly sampled from {y|y_∞≤r̅}, and the noise variable w_ℓ is bounded:
  
      w_ℓ_∞≤C Φ_x(n)_∞x_0_∞ + ∑_ℓ=1^nC Φ_xn(ℓ)_∞η_n-ℓ_∞
      ≤Mmax{σ_0,σ_η}/1-ρ .
  
  
  The following Lemma shows that uniform samples corrupted with independent and bounded noise
  ensure dense sampling of the measurement subspace by providing a high probability lower bound on the coverage s_T(z).
  
  
  Suppose that training data {z_t}_t=1^T is collected with a stabilizing controller satisfying (<ref>) according to Algorithm <ref> with r̅≥ r+Mmax{σ_0,σ_η}/1-ρ + γL_g from a system satisfying (<ref>).
   Then for all z observed from a state x satisfying Cx_∞≤ r,
  
      s_T(z) ≥1/2√(T V_)(γ/r̅ L_g )^p/2
  
  with probability at least 1-δ as long as
  T  ≥ 8V_^-1log(1/δ) ( r̅L_h L_g^2 )^pγ^-p.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  We use this coverage property of the training data and
  the error decomposition presented in Section <ref>  to show our main uniform convergence result.
  
  
  
  
  If training data satisfying (<ref>) is collected with a stabilizing controller satisfying (<ref>) by the sampling scheme in Algorithm <ref> with radius r̅ = √(2)r from
  a system satisfying (<ref>),
  then as long as the system remains within the set {x|Cx_∞≤ r}, the Nadarya-Watson regressor (<ref>)
   will have bounded perception error for every observation z:
  
      h(z) - h(z)_∞≤   γ L_h +  σ_η/T^1/4( L_g √(2) r/γ)^p/4(√(plog(T^2/δ)) +1)
       ,
  
  with probability at least 1-δ as long as γ≤ L_g((√(2)-1)r - Mmax{σ_0,σ_η}(1-ρ)^-1) and
  
  
  
  
  
  
  
   
      T  ≥max{ 8 p V_^-1 (√(2) L_h L_g^2 )^p(r/γ)^plog(  T^2/δ ),  
       V_^-1/3 (24   L_ L_h)^4/3 L_g ^p/3(r/γ)^p+4/3} .
  
  
  
  We present a proof in Appendix <ref>.
  
  
  
  
  
  
  
   
  
  
  
  § CLOSED-LOOP GUARANTEES
  
  
  The previous section shows that nonparametric regression can be successful for learning the perception map within a bounded region of the state space.
  But how do these bounded errors translate into closed-loop performance guarantees, and how can we ensure that states remain within the bounded region?
  To answer this question, we recall the waypoint tracking problem in (<ref>).
  
  
  
  
   §.§ Linear Control for Waypoint Tracking
  
  
  Consider a linear control law for waypoint tracking
  u_t = ∑_k=0^t K^(y)_k y_t-k + ∑_k=0^t K^(r)_k x^_t-k which depends on some output signal y_k = Cx_k +η_k.
  Similar in form to the controller used for sampling (<ref>), this linear waypoint tracking controller can be viewed as computing u_t^ based on waypoints x^_k.
  
  As first discussed in our sampling analysis (<ref>), the closed-loop behavior of a linear system in feedback with 
  a linear controller
  can be described as a linear function of noise variables.
  Example <ref> shows how these system response variables arise from static state estimators and control laws.
  
  
  Consider the classic Luenberger observer,
  
      x_t+1 = A x_t + B u_t + L(y_t - Cx_t) ,
  
  and control inputs chosen as u_t = Kx_t + u^_t, then the closed-loop system has dynamics
  
      [ x_t+1; e_t+1 ] = 
      [ A+BK   BK;    0 A-LC ][ x_t; e_t ] + [ 0; L ]η_t
      + [ B; 0 ] u^_t,
  
  where e_t = x_t- x_t.
  
  
  
  
  
  
  The magnitude of the eigenvalues of A+BK and A-LC thus determine stability and the decay parameter ρ, while the transients determine M.
  
  
  
  
  To facilitate our discussion of the general system response, we will introduce boldface notation for infinite horizon signals and convolutional operators.
  Under this notation, we can write u_t = ∑_k=0^t K_k x_t-k equivalently as u =  K  x.
  
  
  We introduce the signal and linear operator norms
   
      x_∞ = sup_k x_k_∞,  Φ_ = sup_ w_∞≤ 1Φ w_∞ .
  
  These signals and operators can be concretely represented in terms of semi-infinite block-lower-triangular Toeplitz matrices acting on semi-infinite vectors or in the z-domain with x = ∑_k=0^∞ x_k z^-k.
  
  
  Using this representation, a linear controller ( K_y, K_r) induces the
  system responses
  
      =(zI - (A + B  K_y C))^-1      =  B  K_y      =  B  K_r
  
  which are well defined as long as the interconnection is stable.
  Under this definition, the state signal can be written as x = x^ +  n +  x_0.
  The responses  and  can be similarly defined, since u is linear in x and x^.
  
  In Section <ref>, we show how the
  The 
  robust waypoint tracking cost from (<ref>) can be cast as an  norm on system response variables.
  For now,
  For the purposes of our main result, 
  it is only necessary to view system response variables as objects that arise from linear controllers.
  However, system response variables can also be used to synthesize linear controllers.
  This is a key insight of the System Level Synthesis framework, first introduced by <cit.>.
  We will return to this idea in Section <ref> after proving our main result.
  We include further discussion in the full version of this paper <cit.>.
  
  
  
  
  
   §.§ Suboptimality of Certainty-Equivalence
  
  
  
  Suppose that we apply a linear controller to our perception estimates,
  
      u = π( z,  x^) =  K_y h( z) +  K_r  x^ =:  K(h( z),  x^ ).
  
  This is the certainty equivalent controller, which treats the learned perception map as if it is true.
  We will compare this controller with π_⋆ =  K(h(·),·), the result of perfect perception. 
  The suboptimality depends on the following quantity, which bounds C x_∞ under the optimal control law
  
      r_max(Φ) = sup_ x^∈
      x_0_∞≤σ_0C x^+C x_0_ .
  
  The magnitude of this value depends on properties of the considered reference signal class. 
  In Section <ref>, we present the specific form of this quantity for reference signals that are bounded and have bounded differences.
  In the extended version of this paper <cit.>, we present the specific form of this quantity for reference signals that are bounded and have bounded differences.
  
  
  
  
  
  Let  denote the system responses induced by the controller K as in (<ref>), and let c(π_⋆) denote the cost associated with the policy π_⋆ =  K(h(·),·).
  
  Then for a perception component with error bounded by ε_h within the set {x|Cx_∞≤ r},
  the sub-optimality of the certainty-equivalent controller (<ref>) is bounded by
  
      c(π) - c(π_⋆)≤ε_h[ Q^1/2; R^1/2 ]_ .
  
  as long as the sampled region is large enough and the errors are small enough,
  ε_h ≤r - r_max(Φ)/C_.
  
  
  
  
  In signal notation, the cost is given by
  
      sup_ x^∈
      x_0_∞≤σ_0[ Q^1/2 ( x - x^);         R^1/2 u ]_∞
  
  where x and u are the closed-loop trajectories induced by the control policy.
  
  Since both policies use the same linear control law K, they induce the same system response .
  The difference comes from the perception signal.
  The certainty equivalent controller π assigns inputs as
  
      u =  K_y h( z) +  K_r  x^=  K_y C x +   K_y( h( z) - h( z)_ n ) +  K_r  x^ .
  
  While for the optimal controller, u =  K_y C x +  K_r  x^.
  
  Using the system response variables, we can rewrite and upper bound the cost:
  
      c(π)
         =
      sup_ x^∈
      x_0_∞≤σ_0[ Q^1/2      ;       R^1/2 ][          -I      ; K_y C             ][ x_0;  x^;   n ]_∞
         ≤sup_ x^∈
      x_0_∞≤σ_0[ Q^1/2      ;       R^1/2 ][          -I; K_y C       ][ x_0;  x^ ]_∞
      +[ Q^1/2      ;       R^1/2 ][ ;  ] n_∞
         =
      c(π_⋆)+sup_ x^∈
      x_0_∞≤σ_0[ Q^1/2      ;       R^1/2 ][ ;  ] n_∞
         ≤
      c(π_⋆)+[ Q^1/2      ;       R^1/2 ][ ;  ]_·sup_ x^∈
      x_0_∞≤σ_0h( z) - h( z)_∞
  
  
  Recall the uniform error bound on the learned perception map.
  As long as C x_∞≤ r, we can guarantee that h( z) - h( z)_∞≤ε_h.
  Notice that we have 
  
      C x_∞≤sup_ x^∈
      x_0_∞≤σ_0C x^ + C x_0 + C n _≤ r_max(Φ) + ε_h C_ .
  
  Therefore, the result follows as long as ε_h  ≤r-r_max(Φ)/C_.
  
  
  
  
  
  
  
  Thus, the optimal closed-loop system's sensitivity to measurement noise is closely related to the sub-optimality.
  In the next section, we show how to augment the cost of the waypoint tracking problem in (<ref>) to make it more robust to perception errors.
  
  It is possible to use this insight to augment the cost of the waypoint tracking problem in (<ref>) to make it more robust to perception errors <cit.>.
  
  
  
  We now state our main result.
  The proof is presented in the appendix.
  We now state our main result.
  
  Suppose that training data satisfying (<ref>) is collected
  is collected with a stabilizing controller satisfying (<ref>) 
  according in Algorithm <ref> with r̅ = 2 r_max(Φ) ≥max{1, Mmax{σ_0,σ_η}/1-ρ} from
  a system satisfying (<ref>), and that the Nadarya-Watson regressor (<ref>) uses bandwidth γ chosen to minimize the upper bound in (<ref>). 
  Then the overall suboptimality of the certainty equivalent controller (<ref>) is bounded by
  
      c(π) - c(π_⋆)≤ 
        4L_gL_h r_max(Φ)  (4p^2σ_η^4 /T)^1/p+4[ Q^1/2; R^1/2 ]_√(log(T^2/δ))
  
  with probability greater than 1-δ for large enough
  
  
  
  T≥ 4p^2σ_η^4 (10L_gL_hC_√(log(T^2/δ)))^p+4.
  
  
  
   
  
  
  
  § SYNTHESIS OF REFERENCE TRACKING CONTROLLERS
   
  
  This section outlines synthesis strategies for output-feedback linear optimal control problems.
  We begin with a generic overview of system level synthesis, and then explain how to apply the framework to the reference tracking problem that we consider.
  Finally, we extend our result in Proposition <ref> to propose a robust synthesis problem for perception-based control.
  
  
  
  
   §.§ System Level Synthesis
  
  
  Consider an optimal control problem of the form
  
      min_ K     sup_ w_k_∞≤ 1
       n_k_∞≤ 1[ Q^1/2 x_k; R^1/2 u_k ]_∞
            x_k+1 = Ax_k + Bu_k + Hw_k
          y_k = Cx_k + Nn_k
          u_k =  K(y_0:k),
  
  which seeks to find a controller that minimizes the maximum state and input for a linear system driven by bounded process and measurement noise.
  This optimal control problem is an instance of  robust control <cit.>.
  In particular, if the cost matrices are defined such that Q = diag(1/q^2_i) and R = diag(1/r^2_i), then an optimal cost less than 1 guarantees that |x_i,k| ≤ q_i and |u_i,k| ≤ r_i for all possible realizations of process and measurement noise. 
  
  
  
  As discussed in Section <ref> and Section <ref>,
  any linear system in feedback with a linear controller can be written in terms of the system responses {Φ_xw(k), Φ_xn(k), Φ_uw(k), Φ_un(k)},
  
      [ x_k; u_k ] = ∑_t=1^k[ Φ_xw(t) Φ_xn(t); Φ_uw(t) Φ_un(t) ][  Hw_k-t; N n_k-t ][ x; u ] = [  ;   ][ H w; N n ]
  
  where we will use boldface notation for infinite horizon signals and convolutional operators. 
  While we previously considered how linear controllers give rise to system response elements, we will now consider how system response elements can be used to synthesize controllers.
  Equation (<ref>) is linear in the system response elements, so convex functions of state and input translate to convex functions of the system responses. 
  <cit.> show that for any elements  constrained to obey
  
      [ zI-A   -B ] = [ I 0 ] ,   [ zI-A;   -C ]  = [ I; 0 ]
  
  there exists a feedback controller that achieves the desired system responses (<ref>).
  Therefore, any optimal control problem over linear systems can be equivalently written as an optimization over system response elements. 
  Reformulating the optimal control problem (<ref>) yields
  
      min     [ Q^1/2     0;     0 R^1/2 ][ H 0; 0 N ]_    (<ref>),
  
  which is a convex, albeit infinite-dimensional problem.
  In practice, finite-dimensional approximations are necessary, and we briefly describe two that have been successfully applied. 
  The first optimizes over only finite impulse response systems by enforcing that Φ(t) = 0 for all t>T and some appropriately large T.
  This is always possible for systems that are controllable and observable.
  The second approach instead enforces bounds on the norm of Φ(t) for t>T and uses robustness arguments to show that the sub-optimality of this finite dimensional approximation decays exponentially in the approximation horizon T <cit.>.
  
  The synthesis (<ref>) gives rise to a control law of the form u =  K  y where K =  - ^-1. This controller can be implemented via a state-space realization <cit.> or as an interconnection of the system response elements <cit.>.
  
  
  
  
  
  
  
   §.§ Reference Tracking Controllers
  
  
  We now specialize to the linear reference tracking optimal control problem
  
      min_π     
      sup_{x^_k}∈
      w_k_∞≤σ_w
      η_k_∞≤σ_η[ Q^1/2(x_k-x^_k);        R^1/2u_k ]_∞
            x_k+1 = Ax_k + Bu_k +w_k,   y_k = C x_k +η_k,   u_k = π(y_0:k, x^_0:k),
  
  
  Note that in comparison to (<ref>), we generically consider process noise w_k and measurement noise η_k.
  The process noise can encode an initial condition by defining w_-1=x_0.
  In what follows, we assume that signals in the reference class  satisfy boundedness, i.e. x_k^≤ r_max, and bounded differences, i.e. x_k^ - x_k+1^≤Δ.
  
  To use the system level synthesis framework, we reformulate this problem into a disturbance rejection problem.
  Because reference signals in the class  have bounded differences,
  we define the augmented state ξ_k = [x_k-r_k; r_k],  
  disturbances
  ω_k=[w_k/σ_w; (r_k+1-r_k)/Δ], and output y̅_k = [Cx_k; r_k]. 
  Under this change of variables, the optimal control problem can be written as
  
      [                                           min_ u =  Ky̅            sup_ω_k_∞≤ 1
      η_k_∞≤σ_ηQ̅^1/2ξ_k 
       R^1/2u_k_∞;                                              subject to ξ_k+1 = A̅ξ_k + B̅ u_k + H̅ w_k ,   y̅_k = C̅ξ_k + Nη_k;                                                         ]
  
  where Q̅^1/2= [ Q^1/2     0 ] and
  	
      A̅ = [   A A-I;   0   I ],  B̅ = [ B; 0 ],  C̅ = [ C C; 0 I ],  H̅ = [ σ_w I  -Δ I;     0   Δ I ],   
      	N = [ I; 0 ] .
  
  	
  Then as a problem over system response variables :
  
      min     [ Q̅^1/2      0;      0  R^1/2 ][    H̅     0;     0 σ_η N ]_    (<ref>),
  
  The resulting linear controller will be u =  Ky̅ =  K_y  y +  K_r  r, where K =  - ^-1.
  Notice that for the original optimal control problem in (<ref>), we would set σ_η=0 and σ_w = σ_0.
  
  
  
   §.§ Robust Synthesis
  
  
  Using the argument for Proposition <ref>, we can modify the synthesis problem to take into account the limitations of the learned perception map.
  We consider a learned perception map satisfying
  
      h(z_k) - h(z_k)_∞≤_h
  
  as long as Cx_k_∞≤ r.
  Then by using the perception map as a virtual sensor, y_k = h(z_k), we have that y_k = Cx_k + η_k where η_k_∞≤_h as long as Cx_k is bounded.
  
  Then in order to enforce the constraint, 
  
      C  x_∞   ≤C r_∞ + 
      C( x- r)_∞
         ≤ r_max + C[ I 0 ]ξ_∞
         = r_max + C[ I 0 ]
      (H̅ω +  N  n) 
         ≤ r_max + C[ I 0 ]H̅__r_max(Φ) + _hC[ I 0 ] N _≤ r
  
  where we make use of the boundedness of reference signals and derive a specific formula for r_max(Φ).
  
  Therefore, the robust synthesis problem is given by
  
      min     [ Q̅^1/2      0;      0  R^1/2 ][   H̅    0;    0 _h N ]_
           (<ref>),   C[ I 0 ]H̅_ + _hC[ I 0 ] N _≤ r - r_max
  
  The constraint highlights the necessity of achieving low errors _h within a sufficiently large radius r.
  In recent work, <cit.> present a detailed discussion of  controller synthesis for a closely related problem, including its implementation as a linear program. 
  
  
  
  
  § EXPERIMENTS
  
  
  To illustrate our results and to probe their limits, we perform experiments in two simulated environments: a simplified unmanned aerial vehicle (UAV) with a downward facing camera and an autonomous driving example with a dashboard mounted camera.
  All code necessary for reproducing experiments is available at: <github.com/modestyachts/certainty_equiv_perception_control>.
  
  
  
   §.§ Setting and Training Data
  
  For both UAV and car environments, observations are 300× 400 pixel RGB images generated using the CARLA simulator <cit.>. 
  For the UAV setting, we fix the height and orientation of the camera so that it faces downward from an elevation of 40m.
  For the autonomous driving setting, the height is fixed to ground level and the orientation is determined by the car's velocity.
  Figure <ref> shows example observations.
  
  
  0.49
  
  
  
  
  
  In both cases, system dynamics are defined using a hovercraft model, where positions along east-west and north-south axes evolve independently according to double integrator dynamics.
  The hovercraft model is specified by 
  
      A= [   1 0.1   0   0;   0   1   0   0;   0   0   1 0.1;   0   0   0   1 ],   B=[ 0 0; 1 0; 0 0; 0 1 ],   C= [ 1 0 0 0; 0 0 1 0 ] ,
  
  so that x^(1) and x^(3) respectively represent position along east and north axes, while x^(2) and x^(4) represent the corresponding velocities.
  For the UAV, the rendered image depends only on the position, with a scale factor of 20 to convert into meters in CARLA coordinates.
  For the car example, observations are determined as a function of vehicle pose, and thus additionally depend on the heading angle. 
  We defined the heading to be arctan(x^(4)/x^(2)), so the rendered image depends on the position as well as velocity state variables. For the driving setting, the scale factor is 11.
  
  We construct training trajectories by applying a static reference tracking controller to trace circles of varying radius.
  For the training phase, the noisy sensor as gives rise to measurements
  y_k^ = Cx_k + η_k
  where η_k is generated by clipping a Gaussian with standard deviation 0.01 between -1 and 1.
  We use the static reference tracking controller:
  
      u^_k = K(x_k - C^† y^_k),
  
  where the state estimate is computed from y_0:k^ as in Example <ref>.
  The feedback parameter K is generated as the optimal LQR controller when costs are specified as Q=C^⊤ C and R = I while the estimation parameter L is generated as the optimal infinite horizon Kalman filter for process noise with covariance W=I and measurement noise with covariance V=0.1· I.
  We use the periodic reference
  
      y^_k = [ a_ksin(2π k/100) a_kcos(2π k/100) ]^⊤,   a_k = 1.75 + 0.125 (⌊ k/100 ⌋ 4)
  
  which traces circles counterclockwise, ranging in radius from 1.75 to 2.25, or 35-45m for the UAV and 19.25-24.75m for the car.
  We collect training data for 0≤ k≤ T=2,000.
  Figure <ref> and <ref> display the positions from which training observations and measurements are collected.
  Notice that for the car, this strategy results in a sparsely sampled measurement subspace.
  
  
  
  
  
  
  
   §.§ Perception Error Evaluation
  
  
  We consider four types of perception predictors:
  
  	
    * Nadarya-Watson (NW): The estimated position is computed based on training data as in (<ref>) where ρ(z, z_t) = z-z_t_2 is the ℓ_2 distance on raw pixels. The only hyperparameter is the bandwidth γ.
  
  	We investigated a few additional metrics based on ℓ_2 distance between transformed pixels, but did not observe any benefits. The transformations we considered were: 
  	pretrained Resnet-18 features,[<https://github.com/christiansafka/img2vec>]
  	Guassian blur,[<https://scikit-image.org/docs/stable/api/skimage.filters.html#skimage.filters.gaussian>]  
  	and edge detection-type filters.[<https://scikit-image.org/docs/stable/api/skimage.filters.html>]
  	
    * Kernel Ridge Regression (KRR): The estimated position is computed as
  	
      h(z) = [ (y^_0)^⊤        … (y^_T)^⊤ ] (λ I + K)^-1[ k(z_0, z)         … k(z_T, z) ]^⊤
  
  	where the kernel matrix K is defined from the training data with K_ij=k(z_i, z_j) and we use the radial basis function kernel, k(z,z') = e^-αz-z'_2^2. The hyperparameters are regularization λ and spread α.
  	
    * Visual Odometry (VO): This structured method relies on a database of training images with known poses, which we construct using ORB-SLAM <cit.>, and calibrate to the world frame using position measurements {y^_t} which determine scale and orientation.
  	We use only the first 200 training datapoints to initialize this database.
  
  	New observations z are matched with an image z_t in the training data based on “bag of words” image descriptor comparison.
  	Then, the camera pose is estimated to minimize the reprojection error between matched features in z and z_t, and from this we extract the position estimate h(z).
  	
    * Simultaneous Localization and Mapping (SLAM): This structured method proceeds very similarly to the VO method described above, with two key differences.
  	First, all new observations z are added to the database along with training images.
  	Second, pose estimates are initialized based on the previous frame, resulting in a temporal component.
  	We implement this method by running ORB-SLAM online.
  
  These additional methods allow for comparison with a classical nonparametric approach, a classical computer vision approach, and a non-static state-of-the-art approach.
  
  We evaluate the learned perception maps on a grid of 2,500 points, with -2.5≤ x^(1), x^(3)≤ 2.5.
  For the car, we set the angle of the grid points as arctan(-x^(1)/x^(3)) to mimic counter-clockwise driving, which results in a best-case evaluation of the learned perception components.
  For SLAM evaluation, the ordering of each evaluated point matters. 
  We visit the grid points by scanning vertically, alternating upwards and downwards traversal.
  For NW and KRR, we choose hyperparameters which result in low errors within the region covered by training samples. In the UAV setting, we used γ=25,000, α=10^-9, and λ=0.111. 
  In the car setting, we used γ=16666.67.
  
  The resulting errors are displayed for the UAV in
  Figure <ref> and for the car in Figure <ref>.
  The error heatmaps are relatively similar for the three static regressors, with small errors within the training data coverage and larger errors outside of it.
  Though VO has very small errors at many points, its heat map looks much noisier. The large errors come from failures of feature matching within a database of key frames from the training data; in contrast, NW and KRR predictions are closely related to ℓ_2 distance between pixels, leading to smoother errors.
  Because SLAM performs mapping online, it can leverage the unlabelled evaluation data to build out good perception away from training samples.
  In the UAV setting, SLAM has high errors only due to a tall building obstructing the camera view, visible in Figure <ref>.
  Similarly, in the driving setting, a wall and a statue obstruct the view in the locations that SLAM exhibits large errors.
  Figure <ref> and <ref> summarize the evaulations by plotting the median and 99th percentile errors in the inner region of training coverage compared with the outer region. 
  
  
  
  
  
  
  
  
   §.§ Closed-Loop Operation
  
  
  
  Finally, we evaluate the closed-loop performance of the predictors by using them for a reference tracking task.
  We consider reference trajectories of the form
  
      y^_k = [ a sin(2π k/100)  2cos(2π k/100) ]^⊤
  
  and a static reference tracking controller which has the same parameters as the one used to collect training data.
  
  We first examine how changes to the reference trajectory lead to failures in Figure <ref>.
  For the UAV setting, NW with dense sampling is sufficient to allow for good tracking of the reference with a=1.9, but tracking fails when trying to track a reference outside the sampled region with a=1.6.
  As the reference signal drives the system into a sparsely sampled region, errors increase until eventually the UAV exits the region covered by training data.
  Once this occurs, the system loses stability due to the perception failure.
  Despite briefly regaining perception, the system does not recover.
  
  The autonomous driving setting illustrates failure modes that arise for nonparametric predictors when training data is not dense.
  The trajectories in Figure <ref> show that even though the reference is contained within the well-sampled region (a=1.9), NW experiences failures due to neglecting to densely sample with respect to angle.
  Errors cause the system to deviate from the reference, and eventually the system exits the region covered by training data, losing stability due to the perception failure.
  SLAM does not have this problem.
  
  
  
  
  
  
  
  
  
  
   
  
  
  
  § CONCLUSION AND FUTURE WORK
  
  
  
  
  We have presented a sample complexity guarantee for the task of using a complex and unmodelled sensor for waypoint tracking.
  Our method makes use of noisy measurements from an additional sensor to both learn an inverse perception map and collect training data.
  We show that evenly sampling the measurement subspace is sufficient for ensuring the success of nonparametric regression, and furthermore that using this learned component in closed-loop has bounded sub-optimality.
  Unlike related work that focuses on learning unknown dynamics, the task we consider incorporates both a lack of direct state observation and nonlinearity, making it
  relevant to modern robotic systems.
  
  
  
  We hope that future work will continue to probe this problem setting 
  
  to rigorously explore relevant trade-offs.
  One direction for future work is to contend with the sampling burden by collecting data in a more goal-oriented manner, perhaps with respect to a target task or the continuity of the observation map.
  
  
  
  It is also of interest to consider extensions which do not rely on the supervision of a noisy sensor or make clearer use of the structure induced by the dynamics on the observations.
  
  Making closer connections with modern computer vision methods like SLAM could lead to insights about unsupervised and semi-supervised learning, particularly when data has known structure.
  
  
  
   
  
  
    §.§.§ Acknowledgments and Disclosure of Funding
  
  We thank Horia Mania, Pavlo Manovi, and Vickie Ye for helpful comments and assistance with experiments.
  This research is generously supported in part by ONR awards N00014-17-1-2191, N00014-17-1-2401, and N00014-18-1-2833, NSF CPS award 1931853, and the DARPA Assured Autonomy program (FA8750-18-C-0101).
  SD is supported by an NSF Graduate Research Fellowship under Grant No. DGE 1752814
  
  plainnat
  
  
  
  
  
  § TECHNICAL RESULTS
   
  
  In this section, we provide proofs for the results presented in the body of the paper, as well as some intermediate lemmas.
  
  
  
   §.§ Learning Results
  
  
  
  To begin, recall the pointwise error bound presented in Lemma <ref>.
  Its proof relies on the following concentration result, which allows us to handle training data collected from the closed-loop system.
  Care is needed because u_t depends on y_0:t, and a result, z_t = g(x_t) will depend on previous noise variables η_k for k<t.
  
  
  Let (ℱ_t)_t≥ 0 be a filtration, let (V_t)_t≥ 0 be a real-valued stochastic process adapted to (ℱ_t), and let (W_t)_t≥ 1 be a real-valued martingale difference process adapted to (ℱ_t). Assume that W_t |ℱ_t-1 is conditionally sub-Gaussian with parameter σ.
  Then for all T≥ 0, with probability 1-δ,
  
      ∑_k=1^T V_t W_t^2_2 ≤ 2σ^2log(√(∑_t=1^T V_t^2)/δ)(1+∑_t=1^T V_t^2) .
  
  
  
  
  
  
  Recall that the error can be bounded by an approximation term and a noise term:
  
      h(z) - h(z)_∞   = ∑_t=0^T _γ(z_t,z)/s_T(z)(Cx_t +η_t) -  Cx _∞
         ≤∑_t=0^T _γ(z_t,z)/s_T(z)(Cx_t - Cx) _∞ + ∑_t=0^T _γ(z_t,z)/s_T(z)η_t _∞ .
  
  
  The approximation error  is bounded by the weighted average value of Cx_t - Cx _∞ for points in the training set that are close to the current observation.
  Using the continuity of the map h from observations to labels, we have that 
  
      _γ(z_t,z)>0 ρ(z_t, z) ≤γCx_t-Cx_∞≤γ L_h .
  
  This provides an upper bound on the average.
  
  Turning to the measurement error term, we begin by noting that
  
      P(∑_t=0^T _γ(z_t,z)/s_T(z)η_t_∞≥ s)    ≤∑_i=1^p
      P( 
       1/s_T(z)|∑_t=0^T_γ(z_t,z) η_t,i| ≥ s )  .
  
  We then apply Lemma <ref> with ℱ_t = x_0:t, V_t=_γ(z_t,z), and W_t = η_t,i. Note that η_t,i is σ_η/2 sub-Gaussian due to the fact that it is bounded.
  Therefore, with probability at least 1-δ/p^2,
  
      1/s_T(z)|∑_t=0^T_γ(z_t,z) η_t,i|
         ≤σ_η/2 s_T(z)√(2log(p^2/δ√(∑_k=0^T _γ(z_t,z)^2))(1+∑_k=0^T _γ(z_t,z)^2))
         ≤lem1:leq_oneσ_η/2√(2log(p^2/δ√(s_T(z))))√(1+s_T(z))/s_T(z)≤lem1:fracσ_η√(log(p^2√(s_T(z))/δ)/s_T(z))
  
  Where (<ref>) holds since _γ≤ 1, and (<ref>) since s_T(z) ≥ 1 implies that √(1+s_T(z))/s_T(z)≤√(2/s_T(z)).
  Then with probability 1-δ,
  
      ∑_t=0^T _γ(z_t-z)/s_T(z)η_t_∞   ≤σ_η√(log(p^2√(s_T(z))/δ)/s_T(z)) .
  
  
  
  Since Lemma <ref> is only useful for bounding errors for a finite collection of points, we now prove a similar bound that holds over all points.
  While it is possible to use the following result in a data-driven way (with z_i=z_t and H=T), we will use it primarily for our data independent bound.
  
  
  Consider the setting of Lemma <ref>.
  Let {z_i}_i=1^H be any arbitrary set of observations with s_T(z_i)≠ 0.
  Then for all z, the
  learned perception map has bounded errors with probability at least 1-δ:
  
      h(z) - h(z)_∞≤   γ L_h + min_i σ_η/√(s_T(z_i))√(log(p^2H√(s_T(z_i))/δ)) 
      +   2σ_η T/s_T(z_i)L_/γρ(z,z_i) 
       .
  
  
  
  
  
  
  
  
  
  
  To derive a statement which holds for uncountably many points, we adapt the proof of Lemma <ref>.
  Previously, we used the fact that the error can be bounded by an approximation term and a noise term. Now, we additionally consider a smoothness term so that for any 1≤ i≤ H,
  
      h(z) - h(z)_∞
         ≤∑_t=0^T _γ(z_t,z)/s_T(z)(Cx_t - Cx)_∞ +  ∑_t=0^T _γ(z_t,z_i)/s_T(z_i)η_t _∞
                                  + ∑_t=0^T _γ(z_t,z)/s_T(z)η_t- _γ(z_t,z_i)/s_T(z_i)η_t _∞   
         ≤γ L_h +  σ_η/√(s_T(z_i))√(log(p^2H√(s_T(z_i))/δ)) + ∑_t=0^T _γ(z_t,z)/s_T(z)η_t- _γ(z_t,z_i)/s_T(z_i)η_t _∞ .
  
  The final line holds for all z_i with probability at least 1-H·δ/H, following the logic of the proof of Lemma <ref> along with a union bound.
  Now, consider the third term and the boundedness of the noise:
  
      ∑_t=0^T _γ(z_t,z)/s_T(z)η_t- _γ(z_t,z_i)/s_T(z_i)η_t _∞   ≤σ_η∑_t=0^T |_γ(z_t,z)/s_T(z)- _γ(z_t,z_i)/s_T(z_i)| .
  
  Using the fact that each term in the expression is nonnegative,
  
      |_γ(z_t,z)/s_T(z)- _γ(z_t,z_i)/s_T(z_i)|    = 
      1/s_T(z_i)| s_T(z_i)/s_T(z)_γ(z_t,z) - _γ(z_t,z_i) | 
      
      
         ≤1/s_T(z_i)(| _γ(z_t,z) - _γ(z_t,z_i) | + | s_T(z_i)s_T(z)-1 | _γ(z_t,z)  )
  
  Using the smoothness of the kernel, we have that
  
      |_γ(z_t,z)-_γ(z_t,z_i)|    = 
      |(ρ(z_t,z)γ)-(ρ(z_t,z_i)γ)| ≤ L_|ρ(z_t,z) - ρ(z_t,z_i)γ|≤L_/γρ(z,z_i)
  
  where the final inequality uses the fact that ρ is a metric.
  Additionally, we have that
  
      |1-s_T(z_i)s_T(z)|    = 1/s_T(z)|s_T(z)-s_T(z_i)|
         ≤1/s_T(z)∑_t=0^T|_γ(z_t,z)-_γ(z_t,z_i)| 
         ≤1/s_T(z)L_/γ T ρ(z,z_i)
  
  Therefore,
  
      ∑_t=0^T|_γ(z_t,z)/s_T(z)- _γ(z_t,z_i)/s_T(z_i)| 
         ≤∑_t=0^T
      1/s_T(z_i)(L_/γ  + 1/s_T(z)L_/γ T_γ(z_t,z_i) )ρ(z,z) 
         = 
      1/s_T(z_i)(TL_/γ  + ∑_t=0^T _γ(z_t,z) /s_T(z)L_/γ T )ρ(z,z_i) 
         = 
      2T/s_T(z_i)L_/γρ(z,z_i)
  
  The result follows.
  
  
   
  
  
  
  
  We begin by establishing some properties of the training data generated by Algorithm <ref>.
  
      h(z_t)=h(z_n,ℓ) =C x_n,ℓ   = ∑_k=1^n C Φ_xu(k) u^_n-k, ℓ + (C Φ_x(n)x_0,ℓ + ∑_k=1^n C Φ_xn(k) η_n-k, ℓ)
          = [ CΦ_xu(1)        … CΦ_xu(n) ][ CΦ_xu(1)        … CΦ_xu(n) ]^† y^_ℓ+w_ℓ
         
      = y^_ℓ+w_ℓ
  
  where in the second line, we use the fact that the pair (A, B) is controllable implies that the matrix is full column rank.
  In this expression, y_ℓ^ is sampled by Algorithm <ref> uniformly from {y|y_∞≤r̅} and
  
      w_ℓ_∞≤C Φ_x(n)_∞x_0_∞ + ∑_ℓ=1^nC Φ_xn(ℓ)_∞η_n-ℓ_∞≤ M σ∑_ℓ=0^nρ^ℓ≤Mσ/1-ρ ,
  
  where we let σ=max{σ_0,σ_η}
  
  Now, we reason about the density of the training data over the measurement subspace.
  Above, we see that Cx_n,ℓ are generated as the sum of two independent random variables.
  The first is a uniform random variable which has density f_Unif(y) = (2r̅)^-p1{y_∞≤r̅}.
  The second is a bounded random variable, so
  
  
  the support of its density f_w(y) is contained within the set {y_∞≤Mσ/1-ρ}.
  
  We now upper and lower bound the density of each Cx_n,ℓ, which we denote as f. 
  
      f(y)    = ∫_-∞^∞ (2r̅)^-p1{u_∞≤r̅} f_w(u-y)du
          = (2r̅)^-p∫_u+y_∞≤r̅ f_w(u)du 
         ≤ (2r̅)^-p .
  
  
      f(y)     = (2r̅)^-p∫_u+y_∞≤r̅ f_w(u)du 
         ≥ (2r̅)^-p1{y_∞≤r̅ - Mσ1-ρ}∫_u≤Mσ/1-ρ f_w(u)du
          = (2r̅)^-p1{y_∞≤r̅ - Mσ1-ρ} .
  
  The inequality follows by noting that  {u_∞≤Mσ/1-ρ}⊆{u+y_∞≤r̅} whenever y_∞≤r̅ - Mσ/1-ρ.
  
  We now turn our attention to finding a lower bound on s_T(z) = ∑_t=1^T _γ(z, g(Cx_t)).
  We will use Bennett's inequality <cit.>, which requires computing the expectation and second moment of each _γ(z, g(Cx_t)).
  We begin by lower bounding the expected value.
  
      _Cx_t [_γ(z, g(Cx_t))]
         = ∫ K(ρ(g(y), g(u))γ) f(h(u)) du
         ≥lem2:density (2r̅)^-p∫_{u_∞≤r̅ - Mσ/1-ρ}(ρ(z, g(u))γ) d u
         ≥lem2:smoothness (2r̅)^-p∫_{u_∞≤r̅ - Mσ/1-ρ}(L_gh(z)-u_∞γ) d u
         =lem2:inclusion (2r̅)^-p∫(L_gh(z)-u_∞γ) d u
         =lem2:changevarγ^p/(2r̅L_g)^p∫(u_∞) d u
         =lem2:Vker(γ/2r̅L_g)^p 2^p V_
  
  where (<ref>) follows by the lower bound on f(y), (<ref>) follows by the smoothness of g, 
  (<ref>) holds as long as h(z)_∞≤r̅ - Mσ/1-ρ - γL_g which is guaranteed for h(z)_∞≤ r by assumption,
  (<ref>) is a result of a change of variables, and 
  (<ref>) follows by the assumption on .
  Turning to the second moment,
  
      _Cx_t [_γ(z, g(Cx_t))^2]
         = ∫(ρ(g(y), g(u))γ)^2 f(h(u)) du
         ≤lem2:density_up 
      (2r̅)^-p∫(ρ(z, g(u))γ)^2 d u
         ≤lem2:sq_smooth 
      (2r̅)^-p∫(h(z)-u_∞L_h γ) d u
         =lem2:change_var_Lh(γ L_h/2r̅)^p∫(u_∞) d u = (γ L_h/r̅)^pV_
  
  where (<ref>) follows by the upper bound on f(y),  (<ref>) follows by the smoothness of h and the fact that ∈ [0,1], and (<ref>) by a change of variables.
  
  We now bound the deviation
  
  
      P( s_T(z) ≤  T(γr̅L_g)^p V_   -)
         =P( ∑_t=1^T ((γr̅L_g)^p V_- _γ(z,z_t) )≥)
         ≤lem2:Exp_bd P( ∑_t=1^T [_γ(z,z_t)]- _γ(z,z_t) ≥)
         ≤lem2:Bennet
      e^-^2/(2T(γ L_h/r̅)^pV_)
  
  where (<ref>) follows by our lower bound on the expectation and (<ref>) follows by a one-side version of Bennet's inequality for nonnegative random variables, which uses the fact that _γ(z,z_t) ⊥_γ(z,z_k) for k≠ t.
  
  Therefore, with probability at least 1-δ,
  
      s_T(z)    ≥ T V_(γ/r̅L_g)^p - √(2V_ Tlog(1/δ))(γ L_h/r̅)^p/2
         ≥1/2√(T V_)(γ/r̅ L_g )^p/2
  
  where the second inequality holds
  under the assumption that
  T  ≥ 8V_^-1log(1/δ) (r̅L_h L_g^2/γ)^p.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  We are now ready to show the main result by combining Lemma <ref> with Lemma <ref>.
  
  
  
  
  We begin by specifying the set of {z_i} to be used in the application of Lemma <ref>.
  By selecting z_i = g(y_i) for {y_i}_i=1^H defined as an  grid of {y|y_∞≤ r}, we have that for any z, min_iρ(z,z_i) ≤min_iL_hh(z)-y_i_∞≤ L_h. 
  Then notice that an  grid requires H ≥(2r/)^p points, or rearranging, that ≤ 2rH^-1/p.
  Therefore, we have that with probability at least 1-δ/2
  
      h(z) - h(z)_∞≤   γ L_h +  σ_η/√( s_T(z_i_⋆))√(log(2p^2H√(T)/δ)) 
      + 4σ_ηT/ s_T(z_i_⋆)L_/γ L_h rH^-1/p ,
  
  where i_⋆ is the index of the closest element of {z_i}_i=1^H to z.
  
  Next, we use Lemma <ref> to show that each s_T(z_i_⋆) is bounded below.
  First, notice that for r̅ = √(2)r the condition in Lemma <ref> is met by the assumption that
  γ≤ L_g((√(2)-1)r - Mσ/1-ρ).
  Therefore for any 1≤ i≤ H, with probability at least 1-H·δ/(2H), as long as T  ≥ 8V_^-1log(2H/δ) (r̅L_h L_g^2/γ)^p,
  
      s_T(z_i) ≥1/2√(T V_)(γ/r̅ L_g )^p/2=: s_T γ^p/2 .
  
  
  We can therefore select H to balance terms, with
  
      H^1/p
      =4 T L_ L_h r/√(s_T)γ^p+4/4 =4 √(2)T^3/4 L_ L_h r^p+4/4  L_g^p/4/ V_^1/4γ^p+4/4 .
  
  For this choice of H, we have by union bound that with probability at least 1-δ,
  
      h(z) - h(z)_∞≤   γ L_h +  σ_η/√(s_T)γ^p/4(√(log(2p^2H √(T)/δ)) +1)
       .
  
  Bounding the logarithmic term,
  
      log(2p^2H √(T)/δ)   = 
      p  log(2p^2/p(
      4 √(2)T^3/4 L_ L_h r^p+4/4  L_g^p/4/ V_^1/4γ^p+4/4)  
      T^1/2p/δ^1/p)
         ≤plog(24  V_^-1/4 L_ L_h L_g ^p/4( rγ)^p+4/4  T^3p+2/4p /δ^1/p)
         ≤plog( T^2/δ) .
  
  where the first inequality follows because p^2/p≤ 3/√(2) and the final inequality follows due to the assumption that 
  
  (24   L_ L_h)^4/3 V_^-1/3(rγ)^p+4/3  L_g ^p/3≤ T.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  The result follows. It only remains to note that the condition on T in Lemma <ref> is satisfied due to the assumption that
   
      T  ≥  8V_^-1plog(  T^2/δ ) (r̅L_h L_g^2/γ)^p
  
  by noting that log(2H/δ)≤log(2p^2H √(T)/δ)≤plog(  T^2/δ ).
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Performance Results
  
  
  
  
  
  Recall that we wish to bound the difference in cost between π=  K(h(·),·) and π_⋆ =  K(h(·),·).
  The cost is given by
  
      sup_ r∈[ Q^1/2 ( x - r);        R^1/2 u ]_∞
  
  where x and u are the closed-loop trajectories induced by the control policy.
  
  Since both policies use the same linear control law K, they induce the same system response .
  The difference comes from the perception signal.
  The certainty equivalent controller π assigns inputs as
  
      u =  K_y h( z) +  K_r  r=  K_y C x +   K_y( h( z) - h( z)_ n ) +  K_r  r .
  
  While for the optimal controller, u =  K_y C x +  K_r  r.
  
  Using the system response variables, we can write the cost as
  
      c(π)    = sup_ r∈[ Q^1/2 ( x - r);        R^1/2 u ]_∞
      
         =
      sup_ r∈[ Q^1/2      ;       R^1/2 ][          -I      ; K_y C             ][ x_0;   r;   n ]_∞
         ≤sup_ r∈[ Q^1/2      ;       R^1/2 ][          -I; K_y C       ][ x_0;   r ]_∞
      +[ Q^1/2      ;       R^1/2 ][ ;  ] n_∞
         =
      c(π_⋆)+[ Q^1/2      ;       R^1/2 ][ ;  ] n_∞
         ≤
      c(π_⋆)+[ Q^1/2      ;       R^1/2 ][ ;  ]_h( z) - h( z)_∞
  
  
  Recall the uniform error bound on the learned perception map.
  As long as C x_∞≤ r,
  
      h( z) - h( z)_∞≤ε_h .
  
  Notice that we have 
  
      C x_∞≤sup_ r∈ℛC r + C x_0_∞ + ε_h C_≤ r_max(Φ) + ε_h C_ .
  
  Therefore, the result follows as long as ε_h  ≤r-r_max(Φ)/C_.
  
  
  
  
  
  
  
  
  
  To show this result, we combine the expressions in Theorem <ref> and Proposition <ref> for a carefully chosen value of γ.
  To balance the terms, we set (recalling that r̅ = √(2)r = 2r_max(Φ))
  
  
      γ^(p+4)/4 
      = p^1/2σ_η/ L_h√(s_T) 
      = 
      √(2) p^1/2σ_η (2r_max L_g)^p/4/ L_h (T V_)^1/4
   
  Returning to the unsimplified bound (<ref>), this choice of γ results in
  
      h(z) - h(z)_∞≤    (2r_max(Φ) L_gL_h)^p/p+4(4p^2σ_η^4/ T )^1/p+4(√(1/plog(2p^2H √(T)/δ)) +1/√(p) + 1)
       .
  
  
  
  We begin by simplifying the first term. Note that since h∘ g is an identity map,  L_hL_g ≥ 1, so
  (2r_max(Φ) L_gL_h)^p/p+4≤ 2r_max(Φ) L_gL_h since r_max(Φ)≥ 1/2 by assumption.
  
  Next, considering the the logarithmic term:
  
  
  
  
  
      log(2p^2H √(T)/δ)   = 
        plog(2p^2/p(4T L_ L_h (2r_max(Φ))/√(s_T)p^1/2σ_η/ L_h√(s_T))
          T^1/2p/δ^1/p)
         = plog(2p^2/p-1/2(8L_ L_h^2 r_max(Φ) /σ_η)  T^1+1/2p/δ^1/p)
         ≤ 
       plog( 3· 8 L_ L_h^2 r_max(Φ) σ_η ^-1  T^3/2/δ^1/p)
         ≤ 
       plog(  T^2/δ)
  
  where the first inequality follows because p^2/p-1/2≤ 1.5 and the final inequality is true as long as (24 L_ L_h^2 r_max(Φ) σ_η^-1)^2 ≤ T.
  Further simplifying,
  
      √(1/plog(2p^2H √(T)/δ)) +1/√(p) + 1 ≤√(log(  T^2/δ)) +1/√(p) + 1
       ≤ 2√(log(  T^2/δ)) .
  
  The resulting error bound is
  
      h(z) - h(z)_∞≤  4L_gL_h r_max(Φ)  (4p^2σ^4 /T)^1/p+4√(log(T^2/δ)) =: ε_h .
  
  
  Then the result follows by Proposition <ref> as long as
   T≥max{T_1, T_2, T_3, T_4},
  where
  we ensure that the simplification in the logarithm above is valid with 
  
      T_1 = (24 L_ L_h^2 r_max(Φ) σ_η^-1)^2,
  
  we ensure that γ≤ L_g((2-√(2))r_max(Φ) - Mσ/1-ρ) (Theorem <ref>) with
  
      T_2 = (4pσ_η^2)^2 (2r_max(Φ))^p L_g^4/V_ ((2-√(2))r_max(Φ) - Mσ/1-ρ)^p+4L_h^4,
  
  we ensure 
  	T  ≥ 8V_^-1log(2H/δ) (r̅L_h L_g^2γ)^p (Theorem <ref>'s usage of Lemma <ref>) with
  	
      T_3 = V_(8(L_g L_h)^pplog(  T^2/δ ))^p+4/4(
      	 L_g L_h r_max(Φ) /√(2) p^1/2σ_η)^p,
  
  and finally we ensure that  _h≤(√(2)-1) r_max(Φ)/C_ (Proposition <ref>) with
  
      T_4 = 4p^2σ_η^4 (10L_gL_hC_√(log(T^2/δ)))^p+4  .
  
  For large enough values of T, T_4 will dominate.
  
  
  
  
   
  