CS Paper Radar

Learning and Control Beyond Linearity: Towards a Non-asymptotic Theory for Bilinear Systems

Yahya Sattar, Yassir Jedra, Robin Strässer, Frank Allgöwer, Maryam Fazel, Sarah Dean

eess.SY cs.LGcs.ROmath.OCstat.ML ·submitted 2026-09-16 19:34 UTC · v2
benchmark

Abstract

This tutorial provides a unified view of the emerging area of bilinear learning and control. Using linear systems as a benchmark, it explains what fundamentally changes in the bilinear settings, how recent theory addresses finite-sample learning and control, and how these ideas connect to broader themes in nonlinear control, representation learning, and data-driven decision making. For learning, we emphasize tools that are particularly useful in the bilinear settings, such as one-sided Bernstein's inequality for dependent and heavy-tailed covariates, blocking arguments, and martingale concentration for input-dependent noise. We then apply these tools to obtain finite-sample learning guarantees for fully observed bilinear systems, partially observed bilinear systems, and linear systems with bilinear observations. For control, we discuss quadratic control from bilinear observations, where the classical separation principle fails, and review tractable approaches based on belief-space receding horizon control. We also cover stabilization of bilinear dynamics under state feedback using semi-definite programming, LMI relaxations, sum-of-squares methods, and Koopman-based lifting. We conclude by discussing connections to reinforcement learning and machine learning, and some open problems in combined learning and control of bilinear systems.

Closest papers

Nearest neighbours by meaning across the whole index.

Performance Gaps Between Open-Loop, Certainty-Equivalent, and Optimal Control Under Action-Dependent Observations

cs.LG eess.SY ·2026-10-24 ·Leo Maynard-Zhang, Sunmook Choi, Yahya Sattar, Yassir Jedra, Sarah Dean +1 more
similarity 0.64
Abstract

In dynamical systems, feedback can improve performance by allowing decisions to depend on past observations, rather than being designed a priori. Under full observation, the current state is sufficient for decision-making; under partial observation, the controller must instead estimate the state from measurements. When actions also affect observations, control can have a dual role: actions influence both the state and the information available for future decisions. This interaction can invalidate certainty-equivalent (CE) control, a widely used strategy that applies state feedback policies as if the estimated state were the true state. We ask when this suboptimality leads to a quantitative performance gap that grows with the horizon. We study this question in a linear-quadratic system with bilinear observations by comparing the optimal policy, certainty-equivalent control, and the optimal open-loop (OL) policy. We identify an instance-dependent information-strength parameter $q$ and establish distinct performance regimes as $q$ varies. When $q$ is sufficiently small, we show that no policy can improve over OL control by more than $O(1)$ cumulative cost. For large values of $q$, we find that CE achieves an $Ω(T)$ advantage over OL control. Our main finding is that for intermediate values of $q$, we can construct a policy that occasionally probes for information and achieves an $Ω(T)$ advantage over OL control while CE only achieves an $O(1)$ advantage, establishing an $Ω(T)$ gap between CE and optimal control. Our analysis relies on a regret decomposition that captures the tradeoff between the immediate cost of gathering information and its future benefit.

0.24

Bilinear World Models: Learning Representations with Structured Dynamics for Efficient Control

cs.RO eess.SY ·2026-09-28 ·Antonio Pariente, Ignacio Boero, Nikolai Matni, Alejandro Ribeiro
similarity 0.61
Abstract

World models jointly learn latent representations and dynamics that predict how high-dimensional observations evolve under actions. In this work, we propose a JEPA-style world model in which, rather than learning arbitrary latent dynamics, we restrict them to follow a bilinear parameterization. This structure enables efficient planning and control while shifting the modeling burden onto the encoder, encouraging richer representations that expose the controllable geometry of the system. In particular, this structured parameterization allows us to structurally enforce action recoverability, thereby preventing representation collapse by construction. Although prescribing a bilinear parametrization may appear restrictive, we show that a broad class of nonlinear dynamical systems admits a transformation under which the dynamics become bilinear. Empirically, we show across standard 2D and 3D control tasks that representations with bilinear-parameterized dynamics can be learned directly from high-dimensional observations, reducing planning time by nearly three orders of magnitude while retaining or even improving control accuracy. We also propose more demanding regimes of longer-horizon planning and real-time control, and demonstrate that our method succeeds in both, moving JEPA-style world models beyond short-horizon offline planning.

0.47

Optimal input design via Frank-Wolfe

eess.SY math.OC ·2026-09-08 ·Fethi Bencherki, Bruce Lee, Nikolai Matni, Anders Rantzer
similarity 0.61
Abstract · 7 pages, 4 figures

We study optimal input design over a finite horizon for linear dynamical systems. The goal is to minimize a weighted inverse-covariance (information) criterion subject to an energy budget. The set of covariances achievable by causal policies is convex but lacks a tractable explicit description, ruling out projection-based methods. We show that Frank--Wolfe applies naturally: each linear minimization subproblem is a budget-constrained finite-horizon linear quadratic (LQ) problem, solvable by a Riccati recursion and one-dimensional bisection over a Lagrange multiplier. Using smoothness of the objective over the feasible set, we establish an $\mathcal{O}(1/M)$ convergence rate for the objective value, while strong convexity yields an $\mathcal{O}(1/\sqrt{M})$ rate for the iterates. We further extend the framework to input design for system identification with unknown dynamics and adaptive online LQR, and illustrate the approach numerically.

0.28

Learning in Inverse Games: Tractable Training with Probabilistic Guarantees

eess.SY math.OC ·2026-10-02 ·Arghya Mallick, Reza Rahimi Baghbadorani, Peyman Mohajerin Esfahani, Sergio Grammatico
similarity 0.59
Abstract

Inverse game theory seeks to learn agents' unknown objectives from observed equilibrium behavior. Existing residual-based approaches can lead to non-convex problems and need not ensure strong monotonicity of the learned game, limiting reliable equilibrium prediction. We develop a tractable convex framework for learning static and dynamic non-cooperative games using first-order and Nikaido-Isoda (NI) loss. Specialized operator parameterizations, including a Helmholtz--Hodge decomposition in a reproducing kernel Hilbert space (RKHS), enforce strong monotonicity for quadratic, nonparametric, non-quadratic, and linear-quadratic dynamic games. We establish finite-sample out-of-sample prediction guarantees, using Rademacher complexity to match existing bounds for the non-quadratic setting. For noisy sequential data, we develop a robust receding-horizon learning scheme whose adaptive regularization admits a maximum a posteriori (MAP) interpretation and is computed using randomized trace estimation. Numerical experiments, including a stylized autonomous-vehicle collision-avoidance application, demonstrate predictive accuracy and robustness to measurement noise.

0.44

Demystifying Linear Operator Learning for Control Systems

eess.SY cs.LG ·2026-09-16 ·Max Beier, Nicolas Hoischen, Sandra Hirche, Petar Bevanda
published similarity 0.59
Abstract · accepted to the 65th IEEE Conference on Decision and Control; authors' version

This paper proposes a structured approach to learning linear operators for control systems from data. We address both structural and learning-theoretic aspects of the problem. To derive structural assumptions, we propose using the well-established framework of (semi)groups for evolution equations, as operators in control systems are of the same type. Further, we propose analyzing learning algorithms through the lens of the inverse problems framework. This reveals how a learned model depends on the data via error decompositions, convergence guarantees, and optimal regularization -- enabling us to compare existing methods and derive provably advantageous algorithms. In order to obtain these results, we restrict our scope to bounded operators on Hilbert spaces. Although this may appear restrictive, existing approaches often make this assumption implicitly to obtain matrix-like representations. We demonstrate the power of using these frameworks by deriving a convergent estimator for time-varying systems.

0.27

Learning structured linear dynamical systems from missing observations

cs.LG stat.MLeess.SYmath.OC+1 ·2026-10-08 ·Aravinda Kanchana Ruwanpathirana, Hemant Tyagi, Sunny G. W. Wang
similarity 0.59
Abstract · 62 pages, 3 figures

We consider the problem of learning structured linear dynamical systems over convex sets $\mathcal{K}$, where only a small subset of the observations are available at each time point. An estimator which minimizes a bias-corrected, potentially non-convex objective function is proposed. Non-asymptotic bounds are obtained for the statistical error, which depend on the local complexity of $\mathcal{K}$, the trajectory length $T$, and the sub-sampling probability $p$. Convergence of the projected gradient descent algorithm is also established. The general theory is applied to settings where (i) $\mathcal{K}$ is a subspace, (ii) $\mathcal{K}$ is the set of bi-isotonic matrices, and (iii) $\mathcal{K}$ is the set of matrices whose rows are formed by sampling Lipschitz functions. We show meaningful recovery of the transition matrix is possible for values of $T$ much smaller than what is required in the unconstrained case, and for $p = o(1)$.

0.18

Markovian Nonconvex ADMM for Reinforcement Learning: Bellman-Resolvent Stability Beyond Smooth Blocks

cs.LG ·2026-09-29 ·Zhaojun Peng
similarity 0.58
Abstract

We identify and study a structural mechanism for Markovian nonconvex ADMM in reinforcement learning. Using finite discounted MDPs as a canonical proving ground, we show that the discounted Bellman resolvent $(I-γP_π)^{-1}$ can provide the multiplier stability that classical nonconvex ADMM analyses often obtain from a designated smooth block. Starting from this mechanism, we establish convergence under controlled Markov sampling and then under stochastic observations using an empirical Bellman surrogate that jointly represents the random residual and its Jacobian. Markov mixing, initialization drift, observation noise, and decaying bias enter as one operator perturbation, avoiding unbiased product and double sampling requirements. When the perturbations are square summable, the true KKT residual converges almost surely to zero. Under a finite conditional fourth moment condition, a companion iterate satisfies $ \mathbb{E}[\widetilde G_{K+1}] \le A/T+(B/T)\sum_{k<T}m_k^{-1}, $ which becomes $O(T^{-1}+T/N)$ for total Markov sample budget $N$, giving $O(ε^{-1})$ iteration complexity and $O(ε^{-2})$ sample complexity for squared KKT accuracy $ε$. Beyond stationarity, discounted occupancy coverage yields $J^\star-J(π)=O(\sqrt G)$ for direct tabular policies, so covered exact KKT points are globally optimal, while a statewise quadratic Bellman-improvement condition sharpens the relation to $O(G)$. Finally, nonlinear policy, projected Bellman, and explicit occupancy formulations exhibit the same chain of operator invertibility, dual representation, and multiplier stability. This supports discounted operator invertibility as a reusable structural principle for primal-dual reinforcement learning.

0.26

On Convergence of Gradient Temporal-Difference Learning with Regularized Corrections and Eligibility Traces

cs.LG math.OC ·2026-11-04 ·Jingyi Jin, Martha White, Hao Wang
similarity 0.58
Abstract · 66 pages, 1 figure. Submitted to the Journal of Machine Learning Research

Temporal-difference (TD) learning underlies many prediction and control algorithms, but can diverge when combined with off-policy learning, bootstrapping, and function approximation. TD with Regularized Corrections (TDRC) is theoretically sound and practically simple, but existing convergence theory covers only the one-step case under i.i.d. sampling, while the Huber Bellman-error formulation has not been extended to TDRC or eligibility traces. In this work, we establish convergence of constrained TDRC($λ$) with diminishing stepsizes and non-i.i.d. off-policy data, for state-dependent and history-dependent $λ$-parameters. We also propose TDRC($λ$)-Huber, which preserves the TDRC($λ$) fixed point while reducing sensitivity to large Bellman errors. For both algorithms, we apply an ODE-based weak-convergence method from stochastic approximation theory. For the nonlinear mean dynamics of TDRC($λ$)-Huber, we give an integral small-gain condition that guarantees uniqueness and global asymptotic stability of the target equilibrium. We then establish convergence of the constrained algorithm, derive computable sufficient conditions for convergence, and identify a regularization-based convergence mechanism shared by linear TDRC($λ$) and TDRC($λ$)-Huber. When the mean TD matrix is positive stable, both constrained algorithms converge under sufficiently strong regularization without requiring positive definiteness.

0.23