Timezone: »

 
Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds
Yahya Sattar · Zhe Du · Davoud Ataee Tarzanagh · Necmiye Ozay · Laura Balzano · Samet Oymak

@
in Workshop on Reinforcement Learning Theory »
Learning how to effectively control unknown dynamical systems is crucial for autonomous systems. This task becomes more challenging 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 for 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 mixing-time arguments, sample complexity of this algorithm is shown to be $\tilde{\mathcal{O}}(1/\sqrt{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 the proposed adaptive control scheme achieves $\tilde{\mathcal{O}}(\sqrt{T})$ regret, which can be improved to $\hat{\mathcal{O}}(\log(T))$ with partial knowledge of the system. Our analysis introduces innovations to handle MJS specific challenges (e.g. Markovian jumps) and provides insights into system theoretic quantities that affect learning accuracy and control performance.

Author Information

Yahya Sattar (University of California Riverside)
Zhe Du (University of Michigan)
Davoud Ataee Tarzanagh (Michigan)
Necmiye Ozay (University of Michigan)
Laura Balzano (University of Michigan)
Samet Oymak (University of California, Riverside)

More from the Same Authors