Information Theoretic Regret Bounds for Online Nonlinear Control

1 Introduction

• LQRs rarely model global dynamics well, while complex nonlinear systems may require strategic exploration for sample-efficient learning and control.This motivates studying unknown nonlinear dynamics whose mean lies in a known RKHS.Source: §1 · p. 2
• The KNR setting allows discrete or continuous controls and nonsmooth, nondifferentiable dynamics, with additive noise independent across timesteps.The feature map takes state-control pairs into a finite- or countably infinite-dimensional Hilbert space.Source: §1 · pp. 2–3
• Across T episodes, the learner observes each cost function, selects and executes a policy, and seeks low cumulative cost relative to the best feasible controller.The controller maps states and time steps to controls; the best-in-class cost is the minimum over feasible controllers.Source: §1 · p. 3
• LC3 provides regret guarantees for online nonlinear control; the stated finite-dimensional theorem assumes costs in [0,1], finite feature dimension, and bounded features.The paper presents this as an informal specialization of its main result.Source: §1 · p. 3
• The general regret bound has no explicit dependence on RKHS dimension, has H^3 horizon dependence, and is logarithmic in ∥W⋆∥2 and σ2.The authors conjecture the horizon dependence is near optimal.Source: §1 · p. 4
• Under a bounded coefficient-of-variation condition, the improved localized bound has leading regret linear in the best-in-class cost J⋆.The condition holds for LQRs and may hold more generally.Source: §1 · p. 4
• The regret bound needs only second-moment bounds on realized cumulative cost, rather than bounded costs, and thus applies to LQRs.The method also reports competitive results in continuous-control benchmarks, exploration tasks, and dexterous manipulation.Source: §1 · p. 4
• The analysis develops a stopping-time martingale for unbounded realized costs, Gaussian smoothing via chi-squared distance, and a self-bounding link between episode regret and process second moments.The techniques build on linear- and Gaussian-process-bandit analyses but address challenges in the multi-step reinforcement-learning extension.Source: §1 · p. 4

2 Related Work

• Model-based RL and control methods often do not explicitly address exploration or guarantee learned-policy performance; this work focuses on strategic exploration and regret bounds for KNR.The KNR model had prior system-identification results, including Mania et al. [2020].Source: §2 · pp. 4–5
• Prior provably efficient model-based methods have limitations in unbounded-cost LQR analysis, sharp leading-order or localized bounds, and, for some methods, infinite-dimensional settings.The paper distinguishes its results from these methods while noting technical challenges that may aid further continuous-control analysis.Source: §2 · p. 5
• Many online LQR regret analyses use stronger stability and mixing assumptions and evaluate regret on a single trajectory, whereas online KNR uses a more general underlying model.The authors identify this difference as a direction for future work.Source: §2 · p. 5
• Mania et al. [2020] analyze finite-dimensional KNR system identification under reachability and bounded-feature assumptions; this work permits unbounded states and features.The KNR has also been used in practice for system identification.Source: §2 · p. 5

3.1 The Lower Confidence-based Continuous Control algorithm

• LC3 selects an optimistic policy within a confidence region updated from sampled trajectories, using a planning oracle that the paper assumes access to.Computing the optimistic plan is NP-hard; practical approximation algorithms are left for future work.Source: §3.1 · pp. 5–6

3.2 Information Theoretic Regret Bounds

• The information-gain analysis gives γT(λ) = O(dφ log(1+THB²/λ)) for bounded finite-dimensional features, and it can be smaller when policy covariance concentrates in a lower-dimensional subspace.The maximum is over algorithms mapping the history before an episode to its next policy.Source: §3.2 · p. 7

The General Case, with Bounded Moments

• The general regret bound applies to infinite-dimensional RKHSs without uniformly bounded features, assuming nonnegative costs and uniformly bounded second moments of realized cumulative costs from x0.The second-moment assumption is weaker than bounded costs and requires a bound only from the starting state x0; parameter dependencies are logarithmic in ∥W⋆∥² and σ².Source: The General Case, with Bounded Moments · pp. 7–8

The Stabilizing Case, with Bounded Coefficient of Variation

• With bounded coefficient of variation, which holds for LQRs, LC3 has an improved regret bound whose leading term depends on the optimal cost J⋆.For finite-dimensional bounded features, the higher-moment information gain γ2,T is O((dφ log(1+THB²/λ))²).Source: The Stabilizing Case, with Bounded… · pp. 8–9

3.3 Proof Techniques

• The proof controls model-induced cost differences through a self-bounding simulation lemma, using a stopping-time martingale for unbounded realized costs and chi-squared distance to handle Gaussian smoothing.The lemma supports construction of a potential function for analyzing LC3.Source: §3.3 · pp. 9–10

4 Experiments

• Experiments used MPPI for planning and posterior covariance reshaping for Thompson sampling, implementing a Thompson-sampling variation rather than LC3 as analyzed.Evaluations use reward, the negative of cost.Source: §4 · p. 10

4.1 Benchmark Tasks with Random Features

• LC3 with RFFs quickly increased reward and performed well on simple continuous-control tasks, but suffered on contact-rich Hopper as dynamical complexity increased.The authors attribute the Hopper result to non-adaptation of the RFFs and suggest that more interesting scenarios require different feature representations.Source: §4.1 · p. 10

4.2 Exploring the Maze

• In the maze, LC3’s strategic exploration improved success: it reached the goal within 50 episodes, averaging 25.0 episodes to first success, while random walk and PETS-CEM never succeeded.The experiment compared LC3 settings with random walk and PETS-CEM over 50 episodes of trajectory length 30.Source: §4.2 · p. 11, Figure 2 · p. 12

4.3 Practical Application

• Within 10 attempts, LC3 with ensemble features succeeded at dexterous manipulation, while RFF features made no progress and neural-network features made little progress.The 33-degree-of-freedom task requires grasping and lifting an object with unknown dynamics; the ensemble uses predictive outputs from six MuJoCo models with randomized object parameters.Source: §4.3 · p. 12
• The arm-and-hand task’s random-model MPPI baseline moved the hand to the object but could not grasp and lift it.The figure reports performance curves averaged over 12 random seeds.Source: Figure 3 · p. 13

5 Discussion

• The work connects reinforcement-learning theory and control theory, arguing that the KNR model is learnable from a learning-theoretic perspective.The discussion notes that few control-theory results address non-asymptotic sample complexity for controlling unknown dynamics.Source: §5 · p. 13
• The authors argue that sample efficiency may support model learning and control in data-expensive applications involving complex nonlinear dynamics, including dexterous manipulation and medical robotics.They also name human-robot interaction and self-driving cars as potential applications.Source: §5 · p. 13
• Sharp lower bounds remain an open direction, although the results are already minimax optimal for some parameter scalings.Source: §5 · p. 14
• The authors conjecture stronger higher-moment assumptions could improve regret and J⋆ dependence; the current stabilizing-case assumption bounds standard deviation relative to mean.They suggest a bounded variance-to-mean ratio may be needed for the improved J⋆ dependence.Source: §5 · p. 14
• Regret bounds for a single trajectory remain future work and would require stronger stability and mixing assumptions.Source: §5 · p. 14
• Learning a suitable feature space remains an open practical direction because the analysis assumes the RKHS is known.Source: §5 · p. 14

• The section proves the paper’s two main theorems, Theorems 3.2 and 3.8.Source: B Lower Confidence Bound based Analysis · p. 20

B.1 Simulation Analysis

• The proof develops a novel self-bounding simulation lemma using the Optional Stopping Theorem.Source: §B.1 · p. 20
• The proof identifies a Doob martingale and applies Doob’s optional stopping theorem to bound the stopped process.Source: §B.1 · p. 21
• The self-bounding simulation lemma bounds the difference in policy cost under two models in terms of the second moment of realized cumulative cost.The lemma applies to any policy, model parameterization, non-negative cost, and starting state.Source: §B.1 · pp. 22–23

• Under Assumptions 1 and 2, Lemma B.4 gives LC3 a per-episode regret bound.Source: §B.2 · p. 24
• On the confidence-ball event, LC3’s optimistic property and the self-bounding simulation lemma bound the true-model cost difference by a difference under the estimated model.Source: §B.2 · p. 24
• The confidence-ball lemma bounds the sum of failure probabilities for the true dynamics falling outside the confidence balls across episodes.Source: §B.2 · p. 25
• Theorem 3.2’s proof combines the per-episode regret bound, confidence-ball and failure-probability bounds, and V_t ≤ Vmax.Source: §B.2 · p. 26
• Theorem 3.8’s proof applies Assumption 3 on V_t together with the per-episode regret lemma.Source: §B.2 · p. 26

B.3 Confidence Bound and Potential Function Analysis

• The confidence-ball analysis bounds the probability that the true dynamics lie outside the episode’s confidence ball, then assigns inverse-square failure probabilities across episodes.The initial confidence ball contains the true dynamics; for t ≥ 1 the proof uses δ_t = (3/π²)/t².Source: §B.3 · p. 28
• The potential-function proof uses the recursive form of Σ_t and its nonnegative eigenvalues in bounding the trace.Source: §B.3 · pp. 28–29

C Technical Lemmas

• The paper generalizes a self-normalized bound for vector-valued martingales to matrix-valued martingales.Source: C Technical Lemmas · p. 31
• The matrix-valued bound assumes conditionally mean-zero, sub-Gaussian noise and a positive-definite operator, and holds simultaneously for all t with probability at least 1 − δ.Source: C Technical Lemmas · p. 31

• The reported setup includes nine hyperparameter categories, covering MPPI variation and temperature, planning, prior and posterior settings, model updates, and random Fourier features.Source: D Simulation Setups and Results · p. 32
• The authors tuned MPPI parameters on ground-truth models first, then tuned the RFF count and bandwidth, prior parameter, and posterior reshaping constant.Source: D Simulation Setups and Results · p. 32
• Hyperparameters are specified for InvertedPendulum and Acrobot in separate tables.Source: Table 2 · p. 33, Table 3 · p. 33

D.1 Gym Environments

• Across Gym tasks, tested heuristics did not consistently improve performance, and modeling critical interactions such as contacts seems key for Hopper.Increasing the number of RFFs did not significantly reduce modeling error for some contact-rich dynamics such as Hopper.Source: §D.1 · p. 33

D.2 Maze

• The Maze uses continuous states and controls, but its dynamics map control regions to four discrete movement directions, with walls stopping movement.Source: §D.2 · p. 35
• Maze experiments use 100 features for a 100-dimensional one-hot representation, and PETS-CEM uses recommended settings except for a planning horizon matched to MPPI.Source: §D.2 · p. 35

D.3 Armhand with Model Ensemble Features

• The ensemble randomizes object mass, center of mass, inertia, and simulator contact parameters over realistic ranges, allowing different softness and rebound effects.For example, object mass is randomized from 0.1 to 1.0 kg.Source: §D.3 · p. 35, Table 9 · p. 36
• Learned predictive errors across features indicate that the MuJoCo model ensemble successfully captured the true dynamics.Table 10 lists the learned model predictive errors, but the supplied text does not report their values.Source: §D.3 · p. 35, Table 10 · p. 36
• The learned W model combines six ensemble features through weighted diagonal traces and significant off-diagonal values, with generalized positions in the upper block and velocities in the lower block.Accurate velocity prediction is critical to modeling contact forces.Source: Figure 4 · p. 36