# Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds

arXiv: https://arxiv.org/abs/2111.07018 · HTML: https://mlsanity.com/paper/2111.07018/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 29 references that are in the map.
- First posted on arXiv 13 Nov 2021.

## Builds on (most cited first, 14 of 14)

- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [Online Linear Quadratic Control](https://mlsanity.com/paper/1806.07104/) (2018)
- [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020)
- [Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently](https://mlsanity.com/paper/2002.08095/) (2020)
- [Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation](https://mlsanity.com/paper/2007.06482/) (2020)
- [Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification](https://mlsanity.com/paper/1707.04791/) (2017)
- [Stochastic Gradient Descent Learns State Equations with Nonlinear Activations](https://mlsanity.com/paper/1809.03019/) (2018)
- [The Power of Linear Controllers in LQR Control](https://mlsanity.com/paper/2002.02574/) (2020)
- [Mode Clustering for Markov Jump Systems](https://mlsanity.com/paper/1910.02193/) (2019)
- [Certainty Equivalent Quadratic Control for Markov Jump Systems](https://mlsanity.com/paper/2105.12358/) (2021)

## Built on by (most cited first, 14 of 14)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Finite Sample Identification of Bilinear Dynamical Systems](https://mlsanity.com/paper/2208.13915/) (2022)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [Strong Consistency and Rate of Convergence of Switched Least Squares System Identification for Autonomous Markov Jump Linear Systems](https://mlsanity.com/paper/2112.10753/) (2021)
- [Learning Linear Dynamics from Bilinear Observations](https://mlsanity.com/paper/2409.16499/) (2024)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Finite Sample Identification of Partially Observed Bilinear Dynamical Systems](https://mlsanity.com/paper/2501.07652/) (2025)
- [Finite-sample analysis of identification of switched linear systems with arbitrary or restricted switching](https://mlsanity.com/paper/2203.09862/) (2022)
- [Optimal Competitive-Ratio Control](https://mlsanity.com/paper/2206.01782/) (2022)
- [On the Hardness of Learning to Stabilize Linear Systems](https://mlsanity.com/paper/2311.11151/) (2023)
- [System Identification via Nuclear Norm Regularization](https://mlsanity.com/paper/2203.16673/) (2022)
- [Mode Reduction for Markov Jump Systems](https://mlsanity.com/paper/2205.02697/) (2022)
- [Uniform error bounds for quantized dynamical models](https://mlsanity.com/paper/2602.15586/) (2026)
- [Learning switched non-linear dynamical systems from a single trajectory](https://mlsanity.com/paper/2607.23502/) (2026)

## Abstract (arXiv)

Learning how to effectively control unknown dynamical systems is crucial for intelligent autonomous systems. This task becomes a significant challenge when the underlying dynamics are changing with time. Motivated by this challenge, this paper considers the problem of controlling an unknown Markov jump linear system (MJS) to optimize a quadratic objective. By taking a model-based perspective, we consider identification-based adaptive control of MJSs. We first provide a system identification algorithm for MJS to learn the dynamics in each mode as well as the Markov transition matrix, underlying the evolution of the mode switches, from a single trajectory of the system states, inputs, and modes. Through martingale-based arguments, sample complexity of this algorithm is shown to be O(1/√T). We then propose an adaptive control scheme that performs system identification together with certainty equivalent control to adapt the controllers in an episodic fashion. Combining our sample complexity results with recent perturbation results for certainty equivalent control, we prove that when the episode lengths are appropriately chosen, the proposed adaptive control scheme achieves O(√T) regret, which can be improved to O(polylog(T)) with partial knowledge of the system. Our proof strategy introduces innovations to handle Markovian jumps and a weaker notion of stability common in MJSs. Our analysis provides insights into system theoretic quantities that affect learning accuracy and control performance. Numerical simulations are presented to further reinforce these insights.