Relative Almost Sure Regret Bounds for Certainty Equivalence Control of Markov Jump Systems

In this paper, we consider learning and control problem in an unknown Markov jump linear system (MJLS) with perfect state observations. We first establish a generic upper bound on regret for any learning based algorithm. We then propose a certainty equivalence-based learning algorithm and show that this algorithm achieves a regret of O(root T log(T)) relative to a certain subset of the sample space. As part of our analysis, we revisit the switched least squares system identification algorithm of [1], [2] for autonomous MJLS and generalize it to controlled MJLS, establishing strong consistency and almost sure rates of convergence of this method.