[a]organization=Department of Computing and Mathematical Sciences,
addressline=California Institute of Technology, city=Pasadena, postcode=91125,
state=CA, country=USA [*] 11footnotetext: This work is supported by the
National Science Foundation Graduate Research Fellowship under Grant No.
DGE‐1745301 and the Aerospace Corporation.

#  Predictive Control of Linear Discrete-Time Markovian
Jump Systems by Learning Recurrent Patterns

SooJean Han∗ Soon-Jo Chung  John C. Doyle

###### Abstract

Incorporating pattern-learning for prediction (PLP) in many discrete-time or
discrete-event systems allows for computation-efficient controller design by
memorizing patterns to schedule control policies based on their future
occurrences. In this paper, we demonstrate the effect of PLP by designing a
controller architecture for a class of linear Markovian jump systems (MJS)
where the aforementioned “patterns” correspond to finite-length sequences of
modes. In our analysis of recurrent patterns, we use martingale theory to
derive closed-form solutions to quantities pertaining to the occurrence of
patterns: 1) the expected minimum occurrence time of any pattern from some
predefined collection, 2) the probability of a pattern being the first to
occur among the collection. Our method is applicable to real-world dynamics
because we make two extensions to common assumptions in prior pattern-
occurrence literature. First, the distribution of the mode process is unknown,
and second, the true realization of the mode process is not observable. As
demonstration, we consider fault-tolerant control of a dynamic topology-
switching network, and empirically compare PLP to two controllers without PLP:
a baseline based on the novel System Level Synthesis (SLS) approach and a
topology-robust extension of the SLS baseline. We show that PLP is able to
reject disturbances as effectively as the topology-robust controller at
reduced computation time and control effort. We discuss several important
tradeoffs, such as the size of the pattern collection and the system scale
versus the accuracy of the mode predictions, which show how different PLP
implementations affect stabilization and runtime performance.

###### keywords:

Analytic design , Pattern learning , Statistical approaches , Control for
switching systems , Fault tolerant

††journal: Automatica

By considering linear discrete-time Markovian jump systems (MJS) with unknown
mode-switching dynamics, we make concrete the broad notion that controller
synthesis can be made more efficient by reducing computation time and
redundancy via Pattern-Learning for Prediction (PLP), which learns patterns in
the underlying mode process, stores them into memory, and predicts their
future occurrences.

The PLP component of the controller architecture leverages martingale methods
from prior literature, but with two important extensions that make it more
suitable for real-world MJS applications: 1) the distribution of the mode
process is unknown, and 2) the realization of the mode process over time is
not observable.

We apply our proposed architecture to fault-tolerant control of a network with
dynamic topology, and perform an extensive numerical study which compares the
performance of the PLP controller against a baseline and a topology-robust
extension of the baseline. Our study also provides insights into important
tradeoffs that emphasize the impact of PLP, e.g., the size of the pattern
collection and the system scale versus the accuracy of the mode predictions. A
controller with PLP is able to match the control effort of the baseline,
maintain a disturbance-rejection error similar to the topology-robust
controller, and achieve runtime faster than either.

##  1 Introduction

Model-based controller synthesis methods can be developed for stochastic
systems if a theoretical characterization of their stochastic process
distribution exists. In the literature, this concept is most notable for
Gaussian white noise systems (Doyle, 1978; Reif et al., 1999; Theodorou et
al., 2010) or MJS (Xiong et al., 2005; Shi and Li, 2015). Our prior work Han
and Chung (2022) suggested the possibility of expanding such methods to
Poisson shot noise perturbations. For many discrete-time or discrete-event
systems, we can take advantage of the fact that the underlying stochastic
process is a sequence of random variables which occurs as repeated patterns of
interest. For example, in fault-tolerance control or manufacturing process
applications, a pattern of interest may be a specific sequence of modes which
corresponds to a critical system fault (Cho and Lim, 1998; Hanmer, 2013).
Another example can be found in queuing-based systems such as vehicle
intersection networks (Boon and van Leeuwaarden, 2016; van Leeuwaarden, 2006),
where repetition arises naturally when counting entities in the queue over
time.

Learning pattern repetitions in the underlying stochastic process of many
discrete-time or discrete-event stochastic systems allows for at least two
ways of more efficient controller design. First, we may store past sample
paths of the stochastic process into memory so that if a certain pattern
occurs multiple times, we do not need to recompute the corresponding control
policy at every occurrence. Second, we may predict the expected occurrence
times of patterns in the future and schedule to apply the corresponding
control policies at the predicted times. This idea is present in many
applications. For example, a collision-avoidance trajectory over a future
horizon of time can be computed for a moving vehicle based on repeated
experiences of obstacle behavior, instead of relying only on instantaneous
measurements of each obstacle’s position (Richards and How, 2006; Mesquita and
Hespanha, 2012; Shim et al., 2012). In the class of discrete-event systems,
labeled transition representations are invoked to solve fault diagnosis and
prediction problems because they enable easier identification of repeated
patterns over time (Jéron et al., 2008, 2006).

###  1.1 Related Work

Reducing Repetitive Computation: Making control more efficient in terms of
computation time by taking advantage of any repetition in the system behavior
is a fairly common concept in the engineering community. For example, Chen and
Liu (2017) proposes repetitive learning control for a class of nonlinear
systems tracking reference signals that are periodic. Zheng et al. (2021)
discusses a method to approximate linear Gaussian systems using a hidden
Markov model (HMM), then trains it by exploiting its periodic structures. Some
notable machine learning approaches for control, i.e. long short-term memory
networks (LSTMs) and imitation learning (Verma et al., 2018), are also
designed to reduce redundant learning. In fact, the broad class of meta-
learning algorithms refers to algorithms which not only focus on learning the
subject matter (e.g. classification tasks), but also on learning the learning
procedure itself (O’Connell et al., 2022). For problems that can be solved
using deep reinforcement learning methods, experience replay (Fedus et al.,
2020) manages to improve sample and data efficiency by storing the last few
experiences into memory and “replaying” them. A related approach is called
episodic control (Lengyel and Dayan, 2007; Blundell et al., 2016; Pritzel et
al., 2017), which incorporates episodic memory (Botvinick et al., 2019) into
traditional learning techniques with the goal of speeding up training by
recalling specific instances of highly rewarding experiences. Towards this
end, numerous episodic control approaches have been proposed, including model-
free episodic control Blundell et al. (2016) and neural episodic control
Pritzel et al. (2017). In our paper Han et al. (2022), we consider vehicle
traffic congestion control over urban networks of signalized intersections
where the controller architecture leverages an extension of episodic control
which uses equivalence classes to limit the growth of the memory table.

Computing Pattern-Occurrence Quantities: Repetition in stochastic processes
can be addressed in theory by solving “pattern-occurrence problems”, which
characterizes one or more specific sequences of values as “patterns” then
solves for quantities such as the expected time until their next observation
in the stochastic process. Scan statistics (Pozdnyakov and Steele, 2014) is a
popular tool founded on martingale theory, and is often used to characterize
the distribution of pattern occurrences in applications dealing such as fault-
tolerance and anomaly-detection. For example, Guerriero et al. (2009) uses a
scan statistics approach for distributed target-sensing using stationary
sensors and a moving agent under simplified assumptions on the distribution of
the sensors’ positions. Formulas for predicting the occurrence of patterns
have been derived when the patterns emerge from an i.i.d. sequence (see, e.g.,
Li (1980), Gerber and Li (1981), and Pozdnyakov and Kulldorff (2006)) and when
the patterns are generated from scalar Markov chains (Glaz et al., 2006;
Pozdnyakov, 2008).

Controlling Uncertain Systems: One notable drawback to current pattern-
occurrence methods (Pozdnyakov and Kulldorff, 2006; Glaz et al., 2006;
Pozdnyakov, 2008) are their reliance on the assumptions that we are able to
precisely observe the stochastic process and that its distribution is known.
In fact, there is an abundance of research in system identification and data-
driven control, e.g., Dean et al. (2019) and Ho et al. (2021), because these
assumptions often do not hold in real world applications. Ho et al. (2021)
considers robust and adaptive control for nonlinear systems with large model
uncertainties by using a nested convex body chasing approach to optimally
choose an approximate model around which the control law is designed. Many of
these algorithms involve a natural multi-step procedure where the original
uncertain dynamics and constraints are mapped down to an approximate model,
which is then used for planning and control. For example, Nakka et al. (2021)
first develops a surrogate optimization problem with chance constraints by
leveraging polynomial chaos expansion before generating approximate solution
trajectories via sequential convex programming.

Predictions for Structured Control: Using the memorized previous patterns and
state/control trajectories, some algorithms in the literature have also
invoked predictions to reduce redundant computation. Model predictive control
(MPC) (García et al., 1989; A. Cuzzola et al., 2002) is one of the most
popular methodologies that demonstrates this, and both short-term and long-
term predictions for online control have been proven to be beneficial even in
the face of either purely stochastic or adversarial disturbances (Chen et al.,
2015). In Yu et al. (2020), this is demonstrated explicitly by applying greedy
conventional MPC to the linear quadratic tracking problem, and proving near-
optimality in the dynamic regret performance metric. Nagabandi et al. (2018)
provides an architecture which combines learning with MPC for robot link
manipulation tasks; MPC is used for control law design based on the dynamics
of the robotic arm approximated through learning and additional data is used
only if the performance of the current model falls short of the desired goal,
making the entire procedure efficient in time and data consumption. MPC has
also been developed for specific classes of systems; in particular, Park and
Kwon (2002) considers MPC for discrete-time MJS when the dynamics are linear
and uncertain. The benefit of predictions is especially notable when there is
spatial or temporal structure to the problem. Graph neural networks (GNNs)
Battaglia et al. (2018) are an example of a learning-based approach which
encodes the topology of the graph for tasks such as graph classification and
representation learning Kipf and Welling (2017). Recently, extensions of GNNs
are also being used for congestion control problems in computer networks Rusek
et al. (2020) and vehicle traffic forecasting Li et al. (2018); Cui et al.
(2020); both applications deal with large-scale networks for which exploitable
spatial and temporal repetitions are abundant.

###  1.2 Contributions

This paper aims to demonstrate the effectiveness and benefit of Pattern-
Learning for Prediction (PLP) on controller synthesis for a class of linear
MJS whose underlying mode-switching dynamics are unknown. In this context,
“patterns” are recurrent finite-length sequences of modes that arise in the
MJS; PLP uses these patterns to make control design more efficient by
memorizing certain patterns to prevent the re-computation of the control laws
associated with them, then scheduling control laws for patterns that may occur
in the future. Our architecture for the class of uncertain linear discrete-
time MJS consists of three components. First, Mode Process Identification (ID)
uses state and control sequences to learn the unknown statistics of the mode
process; here, these are the transition probability matrix (TPM) and the mode
at the current time. Second, PLP uses the estimated TPM and current mode to
compute quantities pertaining to the future occurrence of patterns. Third,
Control Law Design performs the appropriate optimization to compute the
control law associated with each pattern when it first occurs.

We develop and integrate the PLP component in an otherwise straightforward
architecture which leverages well-researched techniques in system
identification and predictive control. In our analysis of recurring patterns,
we use martingale theory to derive mathematical expressions for two quantities
pertaining to the prediction of patterns: the expected minimum occurrence time
of any pattern from some (user-defined) collection of patterns, and the
probability of a pattern being the first to occur among the collection at the
expected time. Our method operates on two key extensions of prior pattern-
occurrence literature (e.g., Glaz et al. (2006), Pozdnyakov and Steele (2014))
which makes it applicable to real-world dynamics: the distribution of the mode
process is unknown, and the mode process over time is not observable (e.g.,
the past and current modes the system has been in is unknown). To our
knowledge, our proposed architecture is the first to apply a martingale method
to the learning-based control of a stochastic system.

We provide an extensive comparison study that demonstrates the effects of PLP
on a version of the proposed three-part architecture applied to the control of
a network with dynamic topology, where the modes correspond to the different
possible topology variations. For the purposes of this application, the
controller architecture integrates two additional algorithms from existing
literature. First, MPC is used to schedule future control policies to be
applied at the occurrence times specified by PLP. Second, the novel system
level synthesis (SLS) approach Wang et al. (2018); Anderson et al. (2019)
formulates the actual optimization problem to be solved; we especially use the
data-driven formulation (Xue and Matni, 2021; Alonso et al., 2022) because of
the uncertainties in the system. The comparison is performed against two
controllers based on SLS: a baseline SLS controller and an extension of SLS
that was explicitly designed for topology robustness (Han, 2020). Our results
offer insights into several important tradeoffs among four performance metrics
which determine how PLP affects a controller’s performance in stabilizing the
system. Compared to the baseline controller, we show that a PLP controller is
able to achieve better disturbance-rejection at significantly reduced
computation time and redundancy. Furthermore, because Pattern-Learning can be
viewed as an additional mode estimation algorithm for a suitable collection of
patterns, it enables the estimated mode to match the true mode more often than
without Pattern-Learning, boosting system identification performance. We show
that PLP can reject disturbances as well as the topology-robust controller
while consuming less computation time and control effort, then discuss the
role of system scale on PLP design criteria such as the choice of pattern
collection.

###  1.3 Organization

The rest of the paper is organized as follows. In Sec. 2, we introduce the
relevant notations, assumptions, and set up the uncertain linear discrete-time
MJS considered throughout the entire paper. Sec. 3 provides a coherent
overview of the three components that make up our proposed controller
architecture. The subsequent sections go into further detail about the
concrete choice of algorithms used to implement each component: Mode Process
Identification (ID) in Sec. 4, PLP in Sec. 5, and (Predictive) Control Law
Design in Sec. 6. We implement our controller architecture on a topology-
changing network in Sec. 7, and compare its performance against a couple of
baseline controllers without PLP. We conclude the paper in Sec. 8.

Sym. | Definition
---|---
$\Delta T$ |  Timescale of mode w.r.t. system (Assum. 1)
$\hat{\varphi}_{n}^{(t)}$ |  Est. current mode at time $t$, $n\triangleq N[t]$ (Sec. 3.1)
$\hat{P}^{(t)}[m_{1},m_{2}]$ |  Est. TPM entry for $m_{1},m_{2}\in\mathcal{X}$ (Sec. 3.1)
$\mathcal{C}[t]$ |  Set of consistent modes at time $t$ (7)
$\Psi[t]$ |  Time-varying pattern collection (Defs.2,4)
$\bm{\psi}_{k}$ |  A pattern from $\Psi$, enum. $k\in\\{1,\cdots,K\\}$ (Def.2)
$L$ |  Future horizon, pattern length (Def. 4)
$\mathcal{U}$ |  Control law table in memory (Prop. 2)
$\hat{\tau}^{(t)}$ |  Min. occurrence time of $\Psi[t]$ (Def.6, Rmk.6)
$\hat{q}_{k}^{(t)}$ |  First occurrence prob. of $\bm{\psi}_{k}\in\Psi[t]$ (Def.6, Rmk.6)
$\Gamma$ |  Augmented pattern collection (7)
$\bm{\gamma}_{\ell}$ |  Augmented pattern, enum. $\ell\leq\lvert\mathcal{X}\rvert^{2}\lvert\Psi\rvert$ (Def. 8)
$\mathcal{S}_{I}^{(0)}$ |  Set of Case 0 initial-ending strings (Def.9)
$\mathcal{S}_{I}^{(1)}$ |  Set of Case 1 initial-ending strings (Def.9)
$\mathcal{S}_{L}$ |  Set of later-ending strings (Def.9)
$\mathcal{S}$ |  $=\mathcal{S}_{L}\cup\mathcal{S}_{I}=\mathcal{S}_{L}\cup(\cup_{i\in\\{0,1\\}}\mathcal{S}_{I}^{(i)})$ (Def.9)
$K_{I}^{(\chi)}$ |  $=\lvert\mathcal{S}_{I}^{(\chi)}\rvert,\chi\in\\{0,1\\}$ cardinality (Def.9)
$K_{L}$ |  $=\lvert\mathcal{S}_{L}\rvert$ cardinality (Def.9)
$\bm{\beta}_{s}$ |  Ending string in $\mathcal{S}$, enum. $s\in\\{1,\cdots,K_{I}+K_{L}\\}$
$\mathbb{P}(\bm{\beta}_{s})$ |  Prob. that $\bm{\beta}_{s}$ terminates $\\{\xi_{n}\\}$ (Def. 11)
$c_{\ell}$ |  Initial reward of each type-$\ell$ agent (Def.10)
$R_{\tau}^{(\ell)}$ |  Type-$\ell$ cumu. net reward (Def.13)
$R_{\tau}$ |  Cumu. net reward (Def.13)
$W_{s\ell}$ |  Gain matrix entry $(s,\ell)$: total gain earned by
|  type-$\ell$ agent via ending string $\bm{\beta}_{s}$ (Def.12)
Table 1: Summary of some of the notations used in the controller architecture,
listed in pairs of symbols (‘Sym.’) and definitions. Many of these notations
are used to develop the Pattern-Learning component (Sec. 5).

##  2 Setup and Preliminaries

We consider linear Markovian jump systems (MJS) of the following form:

$\displaystyle\hskip 28.45274pt{\bf x}[t+1]$ $\displaystyle=A(\xi_{N[t]}){\bf
x}[t]+B{\bf u}[t]+{\bf w}[t]$ (1)

Here, ${\bf x}[t]{\,\in\,}\mathbb{R}^{n_{x}}$ is the state,
$A(\xi_{N[t]}){\,\in\,}\mathbb{R}^{n_{x}\times n_{x}}$ is the dynamics matrix
which changes according to the phase variable $\xi_{N[t]}$, ${\bf
u}[t]{\,\in\,}\mathbb{R}^{n_{u}}$ is the control input. The external noise
process ${\bf w}[t]{\,\in\,}\mathbb{R}^{n_{x}}$ is unobservable and all we
know about it is its upper norm bound $\left\lVert{\bf
w}[t]\right\rVert_{\infty}{\,\leq\,}\overline{w}$. For each
$t{\,\in\,}\mathbb{N}$, $N[t]$ is the number of modes (i.e., number of phase
switches, or jumps arising from the underlying Markov chain) that have been
observed by time $t$. We say that the current mode-index at time
$t{\,\in\,}\mathbb{N}$ is $n{\,\in\,}\mathbb{N}$ if $N[t]{\,=\,}n$, and the
transition from mode $\xi_{n-1}$ to $\xi_{n}$ occurs at time
$T_{n}{\,\triangleq\,}\min\\{s{\,\in\,}\mathbb{N}\,|\,N[s]=n\\}$. The discrete
mode process $\\{\xi_{n}\\}_{n=1}^{\infty}$ takes values from the set
$\mathcal{X}{\,\triangleq\,}\\{1,\cdots,M\\}$, where $M{\,\in\,}\mathbb{N}$,
and is defined such that $\xi_{n}{\,:\,}\Omega\to\mathcal{X}$ on probability
space $(\Omega,\mathcal{F},\mathbb{P})$ with filtration
$\\{\mathcal{F}_{n}\\}_{n=1}^{\infty}$,
$\mathcal{F}_{n}{\,\triangleq\,}\sigma(\xi_{0},\xi_{1},\cdots,\xi_{n})$. We
assume $B$ is a known constant matrix.

A summary of some of the most important notations used throughout the paper is
provided in Table 1. Throughout this paper, the letter $\xi$ is specifically
reserved to denote random variable modes. We distinguish $\\{\xi_{n}\\}$ from
the sequence of deterministic values $\\{\varphi_{n}\\}$ which it takes, i.e.,
$\xi_{n}{\,=\,}\varphi_{n}$ for all past mode-indices $n{\,\in\,}\mathbb{N}$.
Mode sequences denoted using other Greek letters are deterministic unless
explicitly stated otherwise. We henceforth denote all sequences of the form
$\\{\cdot\\}_{n=1}^{\infty}$ using the shorthand notation $\\{\cdot\\}$, e.g.,
$\\{\xi_{n}\\}_{n=1}^{\infty}{\,\equiv\,}\\{\xi_{n}\\}$ and
$\\{\mathcal{F}_{n}\\}_{n=1}^{\infty}{\,\equiv\,}\\{\mathcal{F}_{n}\\}$, and
denote ${\bf x}[s{\,:\,}t]{\,=\,}\\{{\bf x}[s],\cdots,{\bf x}[t]\\}$ for any
$s{\,<\,}t$, likewise for ${\bf u}[s{\,:\,}t],{\bf w}[s{\,:\,}t]$. For any two
$n,m{\,\in\,}\mathbb{N}$ such that $n_{1}{\,<\,}n_{2}$, we denote random
vectors of mode sequences
$\xi_{n_{1}:n_{2}}{\,\triangleq\,}(\xi_{n_{1}},\xi_{n_{1}+1},\cdots,\xi_{n_{2}})$,
and likewise $\varphi_{n_{1}:n_{2}}$. We denote the concatenation of
$\bm{\alpha}{\,\triangleq\,}(\alpha_{1},\cdots,\alpha_{a})$ and
$\bm{\beta}{\,\triangleq\,}(\beta_{1},\cdots,\beta_{b})$ as
$\bm{\alpha}\circ\bm{\beta}\triangleq(\alpha_{1},\cdots,\alpha_{a},\beta_{1},\cdots,\beta_{b})$,
where $\bm{\alpha}$ and $\bm{\beta}$ are placeholders for either deterministic
or random mode sequences.

######  Assumption 1.

The mode process $\\{\xi_{n}\\}$ operates on a timescale which is $\Delta
T{\,\in\,}\mathbb{N}$ times longer than the timescale of the system (1), i.e.
if $N[t]=n$, then $N[t+a\Delta T]=n+a$ for any $a{\,\in\,}\mathbb{N}$. This
means $T_{n}-T_{n-1}=\Delta T$ for all $n{\,\in\,}\mathbb{N}$. In certain
applications, $\Delta T$ can be interpreted as the minimum time needed between
switching modes, and for simplicity we assume that its value is known.
Consequently, we assume that $N[t]$ and the sequence of transition times
$\\{T_{n}\\}$ are also known.

The mode process $\\{\xi_{n}\\}$ is generated from an irreducible Markov chain
over the state-space $\mathcal{X}$ with transition probability matrix (TPM)
denoted by $P{\,\in\,}\mathbb{R}^{M\times M}$ and initial probability vector
${\bf
p}_{0}{\,\triangleq\,}[\text{p}_{0}(1),\cdots,\text{p}_{0}(M)]^{\top}{\,\in\,}\\{0,1\\}^{M}$.
We represent the entries of the TPM using brackets, so that $P[m_{1},m_{2}]$
denotes the probability of the mode switching from $m_{1}$ to $m_{2}$, for any
$m_{1},m_{2}{\,\in\,}\mathcal{X}$. Suppose the probability distribution of
$\xi_{n}$ is given by ${\bf p}_{n}{\,\in\,}[0,1]^{M}$ at mode-index
$n{\,\in\,}\mathbb{N}$. Then the mode process dynamics are updated in the
usual Markov chain way ${\bf p}_{n+1}^{\top}{\,=\,}{\bf p}_{n}^{\top}P$. This
implies that given $\xi_{n}{\,=\,}\varphi_{n}{\,\in\,}\mathcal{X}$, we have
$\xi_{n+1}{\,=\,}m$ with probability $P[\varphi_{n},m]$ for any
$m\in\mathcal{X}$.

######  Assumption 2.

To demonstrate PLP and focus on the mode process, we take the simpler setting
where the state ${\bf x}[t]$ is fully-observable; we thus design state-
feedback control policies. Following the setup of bounded model errors in
robust control theory, we assume $\overline{w}$ is known or otherwise
attainable from small-gain theorems (Zhou et al., 1996) or techniques based on
structured singular values (Doyle, 1982). For the mode process, in addition to
knowing the values of $\Delta T$, $N[t]$, and $\\{T_{n}\\}$ (see Assumption
1), we consider the following settings. The true realizations
$\\{\varphi_{n}\\}$ of the mode process $\\{\xi_{n}\\}$ are unknown over time,
but the set $\mathcal{X}$ of values that it takes and the initial mode
$\xi_{0}{\,=\,}\varphi_{0}$ are known. The sparsity structure of the TPM $P$
is known, but the values of the nonzero entries are unknown.

##  3 Outline of the Controller Architecture

The controller architecture we propose is visualized in Fig. 1. It consists of
three main parts: 1) Mode Process Identification (ID), 2) Pattern-Learning for
Prediction (PLP) on the mode process, and 3) Control Law Design for the system
dynamics. In this section, we provide a brief description of each
part–including an introduction of the main notations used–to provide a
coherent view of the architecture (Fig. 1) as a whole. The details of each
individual part and the choice of algorithms used to implement them are
discussed in the subsequent sections: Mode Process ID in Sec. 4, PLP in Sec.
5, and Control Law Design in Sec. 6. We emphasize that our choice of algorithm
to implement each component is unique to the uncertain linear discrete-time
MJS setup described in Sec. 2 and that alternative implementations can be made
for other dynamics. For example, in our paper Han et al. (2022), the
controller architecture was designed for the specific application of vehicle
traffic congestion control over urban networks of signalized intersections, in
which the problem is set up as a Markov decision process.

###  3.1 Mode Process Identification Overview

For each time $t{\,\in\,}\mathbb{N}$ and corresponding mode-index
$n{\,\triangleq\,}N[t]$, the system maintains the following estimated
statistics about the mode process $\\{\xi_{n}\\}$ and system dynamics (1): an
estimate $\hat{P}^{(t)}$ of the true TPM $P$, and an estimate
$\hat{\varphi}_{n}^{(t)}$ of the current mode $\varphi_{n}$. The first part of
our architecture, Mode Process Identification (ID), is responsible for
learning these unknown statistics of the mode process. Due to this uncertainty
in the dynamics, we use hats and $(t)$ superscripts to emphasize that these
quantities are estimates which change over time; as we will see in Sec. 4,
this is because modes are estimated based on state and control trajectories
${\bf x}[0{\,:\,}t],{\bf u}[0{\,:\,}t]$.

Figure 1: A flow diagram representation of the proposed controller
architecture specifically for linear MJS dynamics of the form (1). Circles
represent inputs to the algorithm; user-defined inputs are colored blue and
unknown/unobservable parameters are colored gray. The architecture consists of
three main parts (violet boxes): 1) Mode Process ID (Sec. 3.1; Sec. 4), 2)
Pattern-Learning for Prediction (Sec. 3.2; Sec. 5), 3) and Control Law Design
(Sec. 3.3; Sec. 6).

###  3.2 Setup of Pattern-Learning for Prediction

Once $\hat{P}^{(t)}$ and $\hat{\varphi}_{n}^{(t)}$ are obtained from Mode
Process ID (Sec. 3.1) for each $t{\,\in\,}\mathbb{N}$ and
$n{\,\triangleq\,}N[t]$, Pattern-Learning for Prediction (PLP) in Fig. 1
computes additional statistics about the mode process (called the “pattern-
occurrence quantities”) that facilitate the creation of predictions, which
will be used in the Control Law Design component.

######  Definition 1 (Prediction Horizon).

Define the constant $L{\,\in\,}\mathbb{N}$ to be the prediction horizon on the
mode process, i.e., the length of the sequences of modes.

In this paper, “patterns” refer to length-$L$ sequences of modes in the mode
process underlying the system (1), formalized in the following definition.

######  Definition 2 (Patterns).

Let $L{\,\in\,}\mathbb{N}$ be the prediction horizon from Definition 1. Define
the set $\Psi\triangleq\\{\bm{\psi}_{1},\cdots,\bm{\psi}_{K}\\}$ to be a
collection of patterns, where each
$\bm{\psi}_{k}\triangleq(\psi_{k,1},\cdots,\psi_{k,L})$ is a mode sequence
with length $L$ and elements $\psi_{k,j}{\,\in\,}\mathcal{X}$. Each
$\bm{\psi}_{k}$ is referred to as a (mode) pattern if we are interested in
observing its occurrence in the mode process $\\{\xi_{n}\\}$ over time (e.g.,
because it models a system fault).

It is possible for the patterns in $\Psi$ to have different lengths, e.g.,
$\bm{\psi}_{k}\triangleq(\psi_{k,1},\cdots,\psi_{k,d_{k}})$ for any
$d_{k}{\,\in\,}\mathbb{N}$. However, in the context of predicting the future
modes of an MJS like (1), it is probabilistically more likely to observe
patterns with shorter lengths; for balance, we keep each pattern the same
length $L$.

######  Definition 3.

A pattern or an arbitrary sequence of modes $(\alpha_{1},\cdots,\alpha_{a})$
with length $a{\,\in\,}\mathbb{N}$ is feasible with respect to $\hat{P}^{(t)}$
if it can be generated by the Markov chain with TPM $\hat{P}^{(t)}$, i.e.,
$\hat{P}^{(t)}[\alpha_{i},\alpha_{i+1}]>0$ for all
$i{\,\in\,}\\{1,\cdots,a-1\\}$.

Because the statistics of the mode process are estimates instead of true
values, it becomes necessary to consider a pattern collection $\Psi$ (from
Definition 2) which varies with time.

######  Definition 4 (Time-Varying Collection).

We construct the collection of patterns $\Psi[t]$, with time-varying
cardinality $K[t]$, to be a subset of feasible length-$L$ future sequences of
modes given the estimated current mode $\hat{\varphi}_{n}^{(t)}$:

$\displaystyle\Psi[t]$
$\displaystyle\triangleq\\{\bm{\psi}_{1}^{(t)},\cdots,\bm{\psi}_{K[t]}^{(t)}\\}$
$\displaystyle\subseteq\\{\text{feasible
}(\alpha_{1},\cdots,\alpha_{L})|\hat{P}^{(t)}[\hat{\varphi}^{(t)}_{n},\alpha_{1}]>0,\alpha_{i}{\,\in\,}\mathcal{X}\\}$
(2)

######  Definition 5 (Pattern-Occurrence Times).

Denote $n{\,\triangleq\,}N[t]\in\mathbb{N}$ to be the current mode-index at
current time $t{\,\in\,}\mathbb{N}$, and suppose the estimated current mode is
$\xi_{n}{\,=\,}\hat{\varphi}_{n}^{(t)}$. Then for each of the patterns in the
collection $\Psi$ from Definition 2, define the following stopping times for
each $k{\,\in\,}\\{1,\cdots,K[t]\\}$:

$\displaystyle\hskip
8.5359pt\hat{\tau}_{k|n}^{(t)}\\!\triangleq\\!\min\\{i\in\mathbb{N}\,|\,\xi_{n}=\hat{\varphi}_{n}^{(t)},\xi_{n+i-L+1:n+i}\\!\\!=\\!\bm{\psi}_{k}^{(t)}\\}$
(3)

######  Definition 6 (Time and Probability of First Occurrence).

Under the setup of Definition 5 suppose
$\xi_{n+\hat{\tau}_{n}^{(t)}-L+1:n+\hat{\tau}_{n}^{(t)}}=\bm{\psi}_{k}^{(t)}$.
Then define the following for the collection $\Psi$:

$\displaystyle\hskip
14.22636pt\hat{\tau}_{n}^{(t)}\\!\triangleq\\!\\!\min_{k\in\\{1,\cdots,K[t]\\}}\\!\\!\hat{\tau}_{k|n}^{(t)},\hskip
14.22636pt\hat{q}_{k}^{(t)}\\!\triangleq\\!\mathbb{P}(\hat{\tau}_{n}^{(t)}\\!=\\!\hat{\tau}_{k|n}^{(t)})$
(4)

######  Problem 1 (Pattern-Occurrence Quantities).

To generate predictions from the mode process, we are interested in
characterizing the following pattern-occurrence quantities described in
Definition 6.

  * •

the estimate $\mathbb{E}[\hat{\tau}_{n}^{(t)}]$ of the mean minimum occurrence
time, which counts the number of mode-indices to observe the occurrence of any
pattern from $\Psi[t]$, given the estimated current mode
$\hat{\varphi}_{n}^{(t)}$.

  * •

the estimated first-occurrence probabilities
$\\{\hat{q}_{k}^{(t)}\\}_{k=1}^{K[t]}$, where
$\hat{q}_{k}^{(t)}{\,\in\,}[0,1]$ is the probability that pattern
$\bm{\psi}_{k}{\,\in\,}\Psi[t]$ is the first to be observed among all of
$\Psi[t]$.

Again, we keep the hat and superscript $(t)$ in the $\tau$ and $q_{k}$
quantities because we emphasize they are dependent on $\hat{P}^{(t)}$ and
$\hat{\varphi}_{n}^{(t)}$ from Sec. 3.1, which may change over time.

###  3.3 Predictive Control Law Design: General Formulation

Let
$g{\,:\,}\mathbb{R}^{+}\times\mathcal{X}\times\mathbb{R}^{n_{x}}\to\mathbb{R}^{n_{u}}$
be a generic function representing the mode-dependent state-feedback control
law designed by the Control Law Design component in Fig. 1. The Control Law
Design component uses the expected occurrence time
$\mathbb{E}[\hat{\tau}_{n}^{(t)}]$ and probabilities
$\\{\hat{q}_{k}\\}_{k=1}^{K[t]}$ computed from PLP (Sec. 3.2) to store the
control policies of previously-occurred patterns and to schedule control
policies in advance. This procedure is described more carefully in the
following two propositions.

######  Proposition 1 (Scheduling Future Control Inputs).

Suppose we are given the estimated pattern-occurrence quantities
$\mathbb{E}[\hat{\tau}_{n}^{(t)}]$ and $\\{\hat{q}_{k}^{(t)}\\}_{k}$ from PLP.
Let $\tau{\,\equiv\,}\mathbb{E}[\hat{\tau}_{n}^{(t)}]$ be the shorthand
notation (with a temporary abuse of notation) for the estimated expected
minimum occurrence time for the specific pattern collection $\Psi[t]$ given
estimated current mode $\hat{\varphi}_{n}^{(t)}$. To schedule a control law in
advance, we simply choose the pattern $\bm{\psi}_{k}^{(t)}{\,\in\,}\Psi[t]$
corresponding to the largest occurrence probability $\hat{q}_{k}^{(t)}$. Then,
until mode-index $\tau$, the future sequence of control inputs ${\bf
u}[t{\,:\,}T_{n+\tau+1}-1]$ is

$\displaystyle\hskip 28.45274pt{\bf u}[s]$
$\displaystyle=g(s,\psi_{k,1}^{(t)},{\bf x}[s]),\hskip
2.84544pts\in[t{\,:\,}T_{n+1}-1]$ (5) $\displaystyle\vdots$ $\displaystyle{\bf
u}[s]$ $\displaystyle=g(s,\psi_{k,L}^{(t)},{\bf x}[s]),\hskip
2.84544pts\in[T_{n+\lfloor\tau\rfloor}{\,:\,}T_{n+\tau+1}-1]$

Aside from operating on a longer timescale (mode process instead of system
dynamics), Proposition 1 is similar in principle to standard model predictive
control (MPC): only the first control law in the sequence (5), corresponding
to the first mode $\psi_{k,1}^{(t)}$, is applied at the next mode-index
$n{\,+\,}\lfloor\tau\rfloor$.

######  Proposition 2 (Storing Past Control Inputs in Memory).

Define $\mathcal{U}$ to be a table which maps mode patterns
$\bm{\psi}_{k}^{(t)}$ to control policies
$\\{g(t,\psi_{k,1}^{(t)},\cdot),\cdots,g(t,\psi_{k,L}^{(t)},\cdot)\\}$ and the
accumulated state and control trajectories over each occurrence time. When
$\bm{\psi}_{k}^{(t)}{\,\in\,}\Psi[t]$ is first observed, a new entry
$\mathcal{U}[\bm{\psi}_{k}^{(t)}](t)$, defined by (5) for the specific
$\bm{\psi}_{k}^{(t)}$, is created. For anticipated future occurrences of
$\bm{\psi}_{k}^{(t)}$, the system schedules control inputs using
$\mathcal{U}[\bm{\psi}_{k}^{(t)}](t)$ in the form of (5). The entry for
$\bm{\psi}_{k}^{(t)}$ is then updated at every occurrence time after its
first.

Figure 2:  A visualization of PLP with a pattern collection of three patterns
with $L=3$. The middle row of circles shows the evolution of
$\hat{\varphi}_{n}^{(t)}$ over time, while the bottom row of boxes shows the
process on the mode timescale (see Assumption 1). The red circle and box
indicate the estimated mode at current time $t{\,\in\,}\mathbb{N}$. The blue
circles indicate the expected pattern which is first to occur; in this
example, $(3,1,4)$ has the highest first occurrence probability among any
pattern in the collection $\Psi[t]$. Control input sequences are then
scheduled according to Proposition 1, shown in the green box.

Our controller architecture extends traditional uncertain system controllers
(which borrow techniques from system identification and predictive control)
via the incorporation of PLP. We now provide in-depth discussions around each
component in the following Sec. 4, 5, and 6, especially the concrete
algorithms we choose to implement each component for the topology-switching
network application to be demonstrated in Sec. 7. We again emphasize that our
choices were made specifically for the MJS setup in Sec. 2 and that other
implementations of the controller architecture are possible. For example, our
paper Han et al. (2022) describes a version for the problem of vehicle traffic
congestion control, which explicitly includes a memory component to reduce the
size of the table $\mathcal{U}$.

##  4 Mode Process Identification

The Mode Process ID component estimates the current mode
$\hat{\varphi}_{N[t]}^{(t)}$ and the TPM $\hat{P}^{(t)}$. First,
$\hat{\varphi}_{N[t]}^{(t)}$ is estimated using the consistent set narrowing
approach, which is a variation of nested convex body chasing used for model
approximation in Ho et al. (2021). Second, $\hat{P}^{(t)}$ is estimated using
empirical counts based on $\hat{\varphi}_{N[t]}^{(t)}$ and on estimates of the
previous modes $\\{\hat{\varphi}_{N[s]}^{(s)}\\}_{s=0}^{t-1}$.

###  4.1 Consistent Set Narrowing

Because the distribution of the external noise process ${\bf w}[t]$ is unknown
other than its norm bound, we employ consistent set narrowing, which checks
the set of modes that are ‘consistent’ with the state/control trajectories.
This method was employed in $(4)$ of Han (2020) and is similar to the more
general nested convex body chasing approach described in Ho et al. (2021),
which was used for model approximation and selection for designing robust
controls.

Denote the current mode-index as $n{\,\triangleq\,}N[t]{\,\in\,}\mathbb{N}$.
By Assumption 1, there are at most $\Delta T-1$ state and control values,
${\bf x}[T_{n}{\,:\,}t]$ and ${\bf u}[T_{n}{\,:\,}t]$, associated with a
single mode $\varphi_{n}$.

######  Definition 7 (Consistent Sets).

Over time, we construct a sequence of consistent sets
$\\{\mathcal{C}[t]\\}_{t\in\mathbb{N}}$ in the following way. For each
$n{\,\in\,}\mathbb{N}$, we initially set
$\mathcal{C}[T_{n}]{\,\triangleq\,}\mathcal{X}$ because no observations about
the current mode $\varphi_{n}$ have been made yet. Then for each
$t{\,\in\,}(T_{n},T_{n+1})$, if $\mathcal{C}[t-1]{\,\neq\,}\varnothing$, a new
consistent set is formed by retaining all modes $m{\,\in\,}\mathcal{C}[t-1]$
from the previous consistent set $\mathcal{C}[t-1]$ if each one-step value of
state and control $({\bf x}[r],{\bf x}[r+1],{\bf u}[t])$ satisfies the norm-
boundedness condition of the noise ${\bf w}[t]$:

$\displaystyle\mathcal{C}[t]=$
$\displaystyle\bigg{\\{}m\in\mathcal{C}[t-1]\,|\\!\\!\bigwedge\limits_{r=T_{n}}^{t-1}\\!\\!\mathds{1}\\{\left\lVert{\bf
x}[r\\!+\\!1]\\!-\\!A(m){\bf x}[r]\\!-\\!B{\bf
u}[r]\right\rVert_{\infty}\\!\leq\\!\overline{w}\\}\bigg{\\}}$ (6)

As (7) is constructed for each $t{\,\in\,}\mathbb{N}$, we update the mode
estimate
$\hat{\varphi}_{N[t]}^{(t)}\in\text{argmax}_{\zeta\in\mathcal{X}}\hat{P}^{(t-1)}[\hat{\varphi}_{N[t-1]}^{(t-1)},\zeta]$
if $\lvert\mathcal{C}[t]\rvert>1$; otherwise, we update
$\hat{\varphi}_{N[t]}^{(t)}{\,\in\,}\mathcal{C}[t]$.

Figure 3:  A visual diagram depicting Mode Process Identification. Here,
$\Delta T{\,=\,}10$ and $M{\,=\,}5$. With $n\triangleq N[t]$, the upper row of
gray circles denotes a realization $\\{\varphi_{n}\\}$ of the original
unobservable mode process $\\{\xi_{n}\\}$. The middle row denotes the
evolution of the consistent set, updated via (7) using the state and control
trajectories ${\bf x}[T_{n}{\,:\,}t]$, ${\bf u}[T_{n}{\,:\,}t]$. The estimate
$\\{\hat{\varphi}_{n}^{(t)}\\}$ of the mode process is at the bottom row of
white circles.

######  Remark 1.

One property of consistent set narrowing, also observed in nested convex body
chasing approaches (Ho et al., 2021), is that at each time
$t{\,\in\,}\mathbb{Z}^{\geq 0}$, the consistent set $\mathcal{C}[t]$ always
contains the true mode $\varphi_{N[t]}$. This is by definition of the
consistent set, and the deterministic nature of the condition (7) which
defines the narrowing process (equivalent to verifying a simple linear
inequality). In the MJS literature, there have been notions of consistency
similar to (7) according to which unknown modes of MJS are estimated. For
example, Schuurmans and Patrinos (2021) verifies consistency under the
assumption that imperfect measurements ${\bf y}[t]{\,\neq\,}{\bf x}[t]$ of the
state ${\bf x}[t]$ are collected. Thus, instead of using the state history
${\bf x}[0{\,:\,}t]$ directly, the consistency condition is designed around
the collected measurements ${\bf y}[0{\,:\,}t]$ and propagated estimates of
${\bf x}[0{\,:\,}t]$ based on the initial condition ${\bf x}_{0}$ and the
measurement equation.

Mode detectability is also a concept that has been studied; for instance, in
Costa et al. (2015), the mode variable (analogous to
$\xi_{t}{\,\in\,}\mathcal{X}$ in our notation) emits its own signal (analogous
to $\hat{\varphi}_{t}^{(t)}$ in our notation) independently of the system
dynamics and the previous modes. In the consistent set narrowing approach, we
obtain $\hat{\varphi}_{n}^{(t)}$ from the state and control trajectories
$({\bf x}[t],{\bf x}[t+1],{\bf u}[t])$; this estimate also changes with time
as we collect more data about the trajectories.

###  4.2 Empirical Estimation of the TPM

For any $n{\,\in\,}\mathbb{N}$, the estimate of $\varphi_{n}$ is most accurate
when the maximum possible amount of data from the system has been obtained to
create the estimate, i.e., among all $t{\,\in\,}[T_{n},T_{n+1})$, the value of
$\hat{\varphi}_{n}^{(t)}$ is most accurate at time $t{\,=\,}T_{n+1}-1$. For
general $T_{N[t]}{\,<\,}t{\,<\,}T_{N[t]+1}$, $\hat{P}^{(t)}$ is estimated
based on $\hat{\varphi}_{N[t]}^{(t)}$ and only the most accurate estimates of
the previous modes $\\{\hat{\varphi}_{N[s]}^{(T_{N[s]}-1)}\\}_{s=0}^{t-1}$.
Thus, in the TPM estimation procedure, there is only one estimate associated
each true mode $\varphi_{n}$. For simplicity of notation in this section only,
we fix $n{\,\triangleq\,}N[t]$ and denote shorthand
$\hat{\varphi}_{n^{\prime}}{\,\equiv\,}\hat{\varphi}_{n^{\prime}}^{(T_{n^{\prime}}-1)}$
for $n^{\prime}{\,<\,}n$ and
$\hat{\varphi}_{n}{\,\equiv\,}\hat{\varphi}_{n}^{(t)}$.

If $t{\,=\,}T_{n}$ for some $n{\,\in\,}\mathbb{N}$, estimating $\hat{P}^{(t)}$
given $\\{\hat{\varphi}_{n^{\prime}}\\}_{n^{\prime}=1}^{n}$ is
straightforward. By Assumption 2, it is known which entries of the TPM are
nonzero. Thus, we initialize $\hat{P}^{(t)}$ to be an $M\times M$ matrix with
a $1$ in the nonzero entries; when normalized, this corresponds to a
stochastic matrix which has uniform distribution over the feasible transitions
(e.g., $1/3$ probability each for a row with three nonzero entries) but for
estimation purposes, we keep the estimate of the TPM unnormalized until the
end of the simulation duration. For each consecutive pair of transitions
$(\hat{\varphi}_{n^{\prime}},\hat{\varphi}_{n^{\prime}+1})$ for
$n^{\prime}{\,\in\,}\\{0,\cdots,n-1\\}$, we take
$\hat{P}^{(t)}[\hat{\varphi}_{n^{\prime}},\hat{\varphi}_{n^{\prime}+1}]{\,=\,}\hat{P}^{(t)}[\hat{\varphi}_{n^{\prime}},\hat{\varphi}_{n^{\prime}+1}]+1$.

If $T_{n}{\,<\,}t{\,<\,}T_{n+1}$ for some $n{\,\in\,}\mathbb{N}$, we have two
separate subcases. If
$\hat{\varphi}_{n}^{(t-1)}{\,=\,}\hat{\varphi}_{n}^{(t)}$, then we simply
follow the approach above and compute $\hat{P}^{(t)}$ using the sequence
$\\{\hat{\varphi}_{n^{\prime}}\\}_{n^{\prime}=1}^{n}$. Otherwise, if
$\hat{\varphi}_{n}^{(t-1)}{\,\neq\,}\hat{\varphi}_{N[t]}^{(t)}$, then we again
follow the approach above and compute $\hat{P}^{(t)}$, but using the sequence
$\\{\hat{\varphi}_{n^{\prime}}\\}_{n^{\prime}=1}^{n-1}$ instead. To
incorporate the mode estimate at current mode-index $n$, we first need to
reset the TPM estimate of the last transition via
$\hat{P}^{(t)}[\hat{\varphi}_{n-1},\hat{\varphi}_{n}^{(t-1)}]{\,=\,}\hat{P}^{(t)}[\hat{\varphi}_{n-1},\hat{\varphi}_{n}^{(t-1)}]{\,-\,}1$;
then we update as usual
$\hat{P}^{(t)}[\hat{\varphi}_{n-1},\hat{\varphi}_{n}^{(t)}]{\,=\,}\hat{P}^{(t)}[\hat{\varphi}_{n-1},\hat{\varphi}_{n}^{(t)}]{\,+\,}1$.
Once the mode sequence estimates have been processed until current time $t$,
we update $\hat{P}^{(t)}$ such that each row is normalized to sum to $1$.

######  Remark 2.

The need for including Mode Process ID in the controller architecture Fig. 1
is closely related to the notion of mode observability, which has been studied
extensively in the literature (Vidal et al., 2002; Alessandri et al., 2005;
Baglietto et al., 2007; Schuurmans and Patrinos, 2021). One common setup is
that the measurements come from a (linear) noisy measurement equation such
that ${\bf y}[t]{\,\neq\,}{\bf x}[t]$, and derive mode observability
conditions from the imperfect observations ${\bf y}[t]$ of the state ${\bf
x}[t]$. Also, the mode process is assumed to operate on the same timescale as
the system dynamics. Compared to these methods, the algorithms we chose for
implementing Mode Process ID hinge upon assumptions that simplify the mode
observability problem. For example, in Assumption 2, the state ${\bf x}[t]$ is
observable and in Assumption 1, we fix the mode switching times to be constant
and deterministic rather than stochastic.

We again emphasize that this is because the focus of our paper is on the
impact of PLP on control design rather than mode observability, and we aimed
to set up a simple scenario to show that our approach can be used when the
system has uncertainties. Thus, not all of our assumptions are limiting; for
example, compared to our approach, Vidal et al. (2002) explicitly imposes that
the external noise processes $\\{{\bf w}[t]\\}_{t},\\{{\bf v}[t]\\}_{t}$ are
Gaussian white and neither Vidal et al. (2002) nor Alessandri et al. (2005)
consider the impact of control.

######  Remark 3.

We qualitatively discuss some conditions for mode observability in our
specific implementation of Mode Process ID. First, the modes
$\\{A(1),\cdots,A(M)\\}$ cannot be too “similar” to each other with respect to
a certain metric $d$, (e.g., if $d(A(m_{1}),A(m_{2})){\,<\,}\epsilon$ for some
threshold $\epsilon{\,>\,}0$ and two distinct modes $m_{1}{\,\neq\,}m_{2}$ and
$m_{1},m_{2}{\,\in\,}\mathcal{X}$). Second, when $\Delta T$ is too short, the
consistent set may not converge to a single mode even if
$d(A(m_{1}),A(m_{2})){\,\geq\,}\epsilon$ for all pairs
$(m_{1},m_{2}){\,\in\,}\mathcal{X}$ such that $m_{1}{\,\neq\,}m_{2}$. Rigorous
derivation of these conditions for our specific use case are deferred to
future work. This includes designing $d$ and $\epsilon$ for the consistent set
narrowing approach, and deriving conditions on $\Delta T$ and the set
$\\{A(1),\cdots,A(M)\\}$ for guaranteed convergence towards a singleton
consistent set. Although these conditions are contingent upon our simplifying
assumptions, they are expected to be similar to those derived in the
aforementioned literature. For the purposes of our simulations in Sec. 7,
$\Delta T$ and the different modes are empirically selected.

##  5 Pattern-Learning for Prediction

The Pattern-Learning component is implemented by using martingale theory to
derive closed-form expressions about the pattern-occurrence quantities from
Problem 1, which are two important statistics that will aid with prediction on
the mode process. With martingales, the resulting formulas yield better
mathematical interpretation. In scan statistics, martingales also allow for a
more accurate test of experiment results than hypothesis testing (Guerriero et
al., 2009).

###  5.1 Construction Based on Game Interpretation

######  Remark 4.

We simplify the notation and remove the hats and the superscripts of $(t)$ in
the estimated quantities throughout Sec. 5 only. That is, for each $n$ and $t$
satisfying $N[t]{\,=\,}n$, we denote
$\varphi_{n}{\,\equiv\,}\hat{\varphi}_{n}^{(t)}$,
$P{\,\equiv\,}\hat{P}^{(t)}$, $\tau_{k|n}{\,\equiv\,}\hat{\tau}_{k|n}^{(t)}$,
$\tau_{n}{\,\equiv\,}\hat{\tau}_{n}^{(t)}$, and
$q_{k}{\,\equiv\,}\hat{q}_{k}^{(t)}$. Furthermore, we also remove the bracket
$[t]$ in the pattern collection $\Psi[t]$ (see Definition 4), and use the
notation $\Psi$ instead. However, we emphasize the understanding that the
computation done at time $t$ uses the original estimates and the time-varying
pattern collection.

Note that there are constraints on the degrees of freedom on possible Markov
chain sample path trajectories. Thus, we take inspiration from Pozdnyakov
(2008) and consider the occurrence of feasible augmented patterns up to two
extra modes.

######  Definition 8 (Augmented Pattern).

Suppose we are given a collection of patterns $\Psi$ (from Definition 4). An
augmented pattern $\bm{\gamma}$ corresponding to a pattern
$\bm{\psi}_{k}{\,\in\,}\Psi$ is defined by prefixing two modes
$m_{1},m_{2}{\,\in\,}\mathcal{X}$ such that the resulting sequence is feasible
in the sense of Definition 3. We define the augmented collection

$\displaystyle\Gamma\triangleq\\{\text{feasible
}(m_{1},m_{2})\circ\bm{\psi}_{k}\hskip 2.84544pt|\hskip
2.84544ptm_{1},m_{2}\in\mathcal{X};\bm{\psi}_{k}\in\Psi\\}$ (7)

to be the collection of augmented patterns, and we define
$K_{L}{\,\in\,}\mathbb{N}$ to be its cardinality. We enumerate each augmented
pattern $\bm{\gamma}_{\ell}$ in the augmented collection $\Gamma$ using
subscript $\ell{\,\in\,}\\{1,\cdots,K_{L}\\}$. Here, $\circ$ denotes the
concatenation operation and each augmented pattern has length $L+2$.

It is easier to solve for Problem 1 by conditioning on observing specific
types of ending strings, formally defined below.

######  Definition 9 (Ending Strings).

Given the collection of patterns $\Psi$ and current mode-index
$n{\,\in\,}\mathbb{N}$, suppose we let the mode sequence
$\\{\xi_{n},\xi_{n+1},\cdots\\}$ run until one of the patterns from $\Psi$ has
been observed. Then an ending string associated with pattern
$\bm{\psi}_{k}{\,\in\,}\Psi$ terminates the mode process at mode-index
$\tau_{n}{\,>\,}n$ if $\xi_{\tau_{n}-L+1:\tau_{n}}{\,=\,}\bm{\psi}_{k}$. We
characterize two primary types of ending strings:

  * •

An initial-ending string $\bm{\beta}$ occurs when part of an augmented pattern
is observed immediately after the current mode. We classify initial-ending
strings into two further subcases:

    * –

A Case $0$ initial-ending string $\bm{\beta}{\,\triangleq\,}\bm{\psi}_{k}$
occurs when $\xi_{n+1:n+L}{\,=\,}\bm{\psi}_{k}$. Define
$\mathcal{S}_{I}^{(0)}$ to be the set of Case 0 initial-ending strings with
cardinality $K_{I}^{(0)}{\,\in\,}\mathbb{N}$.

    * –

Let $m_{1}{\,\in\,}\mathcal{X}$ be such that the above ending strings are
feasible. A Case $1$ initial-ending string
$\bm{\beta}\triangleq(m_{1})\circ\bm{\psi}_{k}$ occurs when
$\xi_{n+1:n+L+1}=(m_{1})\circ\bm{\psi}_{k}$. Define $\mathcal{S}_{I}^{(1)}$ to
be the set of Case 1 initial-ending strings with cardinality
$K_{I}^{(1)}\in\mathbb{N}$.

  * •

Let $m_{1},m_{2}{\,\in\,}\mathcal{X}$ be such that the above ending strings
are feasible, and let $*$ be a placeholder for any feasible sequence of modes
(see Definition 3) including the empty string. A later-ending string
$(*,m_{1},m_{2})\circ\bm{\psi}_{k}$ occurs when an augmented pattern is
observed long after the current mode, i.e., when $\tau_{n}>n+L+1$ and
$\xi_{\tau_{n}-L+1:\tau_{n}}{\,=\,}(m_{1},m_{2})\circ\bm{\psi}_{k}$. Define
$\mathcal{S}_{L}\triangleq\\{(*)\circ\bm{\gamma}_{\ell}\,|\,\bm{\gamma}_{\ell}\in\Gamma\\}$
to be the set of later-ending strings, with the same cardinality $K_{L}$ as
$\Gamma$.

Define
$\mathcal{S}_{I}{\,\triangleq\,}\mathcal{S}_{I}^{(0)}\cup\mathcal{S}_{I}^{(1)}$
with cardinality $K_{I}{\,=\,}K_{I}^{(0)}+K_{I}^{(1)}$, and let the set of
ending strings be $\mathcal{S}=\mathcal{S}_{I}\cup\mathcal{S}_{L}$. We
enumerate each ending string $\bm{\beta}_{s}$ in $\mathcal{S}$ using the
subscript $s{\,\in\,}\\{1,\cdots,K_{I}+K_{L}\\}$.

Figure 4:  A visualization of the ending strings and agent-reward construction
using the setup of Example 1. The red box marks the current mode-index
$n\in\mathbb{N}$, and each of the three sequences demonstrate the three
different types of ending strings which terminate the mode process in the
sense of Definition 9. The grey rectangles hide future modes which have not
occurred because of termination. For the last case where $\bm{\gamma}_{13}$
terminates the mode process as a later-ending string, type-$13$ agents at
mode-indices $1,2,\cdots,\tau_{3}-5$ are shown. By the reward construction of
Definition 10, type-$13$ agent $\tau_{3}-5$ is the only agent who receives a
nonzero reward.

######  Example 1 (Ending Strings Construction).

We provide intuition behind the notation described by Definition 9. Let
$M{\,=\,}4$, i.e., $\mathcal{X}{\,=\,}\\{1,2,3,4\\}$, and let the (estimated)
TPM $P$ be such that $P[m_{1},m_{2}]{\,>\,}0$ for all
$m_{1},m_{2}{\,\in\,}\mathcal{X}$ except when $m_{1}{\,=\,}m_{2}$ and when
$(m_{1},m_{2}){\,\in\,}\\{(3,2),(2,3),(3,4),(4,3)\\}$. The pattern collection
consists of $K{\,=\,}3$ patterns
$\Psi{\,=\,}\\{\bm{\psi}_{1},\bm{\psi}_{2},\bm{\psi}_{3}\\}$ of length
$L{\,=\,}3$, with $\bm{\psi}_{1}{\,=\,}(213)$, $\bm{\psi}_{2}{\,=\,}(412)$,
and $\bm{\psi}_{3}{\,=\,}(314)$. The augmented pattern collection is defined
as $\Gamma{\,\triangleq\,}\cup_{i=1}^{3}\Gamma_{i}$ with
$\Gamma_{1}{\,=\,}\\{\bm{\alpha}\circ\bm{\psi}_{1}|\bm{\alpha}{\,\in\,}\\{(14),(21),(24),(31),(41)\\}\\}$,
$\Gamma_{2}{\,=\,}\\{\bm{\alpha}\circ\bm{\psi}_{2}|\bm{\alpha}\in\\{(12),(21),(31),(41),(42)\\}\\}$,
$\Gamma_{3}{\,=\,}\\{\bm{\alpha}\circ\bm{\psi}_{3}|\bm{\alpha}\in\\{(21),(31),(41)\\}\\}$.
The number of later-ending strings is $K_{L}{\,=\,}13$. Suppose the
(estimated) current mode is $\varphi_{n}{\,=\,}2$. The set of feasible
augmented Case 0 initial-ending strings is
$\mathcal{S}_{I}^{(0)}{\,=\,}\\{\bm{\psi}_{2}\\}$ since $P[2,4]{\,>\,}0$. For
Case 1 initial-ending strings,
$\mathcal{S}_{I}^{(1)}{\,=\,}\\{(1)\circ\bm{\psi}_{1},(4)\circ\bm{\psi}_{1},(1)\circ\bm{\psi}_{2},(1)\circ\bm{\psi}_{3},(2)\circ\bm{\psi}_{2}\\}$.
Thus, $K_{I}^{(0)}{\,=\,}1$ and $K_{I}^{(1)}=4$.

######  Definition 10 (Agents).

Let $\Gamma$ be the augmented pattern collection associated with original
collection $\Psi$ (see Definition 8). We introduce the notion of an agent,
which observes the mode process $\\{\xi_{n}\\}$ and accumulates rewards at
each mode-index with the goal of observing a pattern from $\Gamma$
(vicariously observing a pattern from $\Psi$). We refer to a type-$\ell$ agent
to be an agent which accumulates rewards by specifically observing the
occurrence of $\bm{\gamma}_{\ell}{\,\in\,}\Gamma$ in $\\{\xi_{n}\\}$. At each
mode-index $n{\,\in\,}\mathbb{N}$, $K_{L}$ new agents, one for each type
$\ell$, $\ell{\,\in\,}\\{1,\cdots,K_{L}\\}$, are introduced to the mode
process; we refer to a type-$\ell$ agent which is introduced at mode-index $n$
as type-$\ell$ agent $n$. A type-$\ell$ agent $n$ observes (estimated) mode
realizations in the future sequence $\\{\xi_{n+1},\xi_{n+2},\cdots,\\}$ and
accumulates rewards at a rate which is inversely-proportional to the action it
took, starting with some arbitrary initial reward
$c_{\ell}{\,\in\,}\mathbb{R}$. If $\varphi_{n}{\,=\,}m_{1}$, type-$\ell$ agent
$n$ aims to observe the event
$\\{\xi_{n+1:n+L+1}{\,=\,}(m_{2})\circ\bm{\psi}_{k}\\}$. Otherwise, if
$\varphi_{n}{\,\neq\,}m_{1}$, type-$\ell$ agent $n$ aims to observe the event
$\\{\xi_{n+1:n+L}{\,=\,}\bm{\psi}_{k}\\}$.

######  Remark 5.

It becomes necessary to distinguish the occurrence time of a pattern
$\bm{\psi}_{k}$ from that of an augmented pattern
$\bm{\gamma}_{\ell}\triangleq(m_{1},m_{2})\circ\bm{\psi}_{k}$. We define
$\tau_{\ell|n}^{a}$ and $\tau_{n}^{a}$ to be the versions of (3) and (4) for
$\gamma_{\ell}\in\Gamma$.

######  Remark 6.

Due to the stationarity of $\\{\xi_{n}\\}$, the distributions of
$\tau_{k|n_{1}}{\,-\,}n_{1}$ and $\tau_{k|n_{2}}{\,-\,}n_{2}$ are equivalent
for each $k{\,\in\,}\\{1,\cdots,K\\}$, and any mode-indices
$n_{1},n_{2}{\,\in\,}\mathbb{N}$, such that
$\varphi_{n_{1}}{\,=\,}\varphi_{n_{2}}$. Likewise, the distributions of
$\tau_{n_{1}}-n_{1}$ and $\tau_{n_{2}}-n_{2}$ are equivalent. For notation
simplicity in the following presentation, we remove the subscript
$n\in\mathbb{N}$ in all variables, and use the above stationarity property to
shift mode-indices to $n{\,=\,}0$ in variables such that the current mode is
given by $\varphi_{0}$ instead of $\varphi_{n}$. Furthermore, we apply the
shorthand notation to Definitions 5 and 6 such that
$\tau_{k}{\,\equiv\,}\tau_{k|0}$ and $\tau{\,\equiv\,}\tau_{0}$; the notation
for the augmented patterns (Remark 5) follow similarly as
$\tau_{\ell}^{a}{\,\equiv\,}\tau_{\ell|0}^{a}$ and
$\tau^{a}{\,\equiv\,}\tau_{0}^{a}$.

######  Definition 11 (Ending String Probabilities).

Define $\mathbb{P}(\bm{\beta}_{s})$ to be the probability that an ending
string $\bm{\beta}_{s}{\,\in\,}\mathcal{S}$ terminates the mode process
$\\{\xi_{n}\\}$ in the sense of Definition 9. For initial-ending strings
$\bm{\beta}_{s}{\,\in\,}\mathcal{S}_{I}$ which is explicitly denoted as
$(\beta_{1},\cdots,\beta_{b_{s}})$ with length $b_{s}{\,\in\,}\mathbb{N}$, we
get
$\mathbb{P}(\bm{\beta}_{s}){\,=\,}P[\varphi_{0},\beta_{1}]\prod_{j=1}^{b_{s}-1}P[\beta_{j},\beta_{j+1}]$.
We demonstrate how to compute $\mathbb{P}(\bm{\beta}_{s})$ for later-ending
strings $\bm{\beta}_{s}{\,\in\,}\mathcal{S}_{L}$ in the following Sec. 5.2, as
part of solving Problem 1.

######  Definition 12 (Gain Matrix).

Let $\bm{\beta}_{s}{\,\in\,}\mathcal{S}$ be an ending string which is
explicitly denoted as
$\bm{\beta}_{s}{\,\triangleq\,}(\beta_{1},\cdots,\beta_{b_{s}}){\,\in\,}\mathcal{S}$
with length $b_{s}{\,\in\,}\mathbb{N}$. Further let augmented pattern
$\bm{\gamma}_{\ell}{\,\in\,}\Gamma$ be associated with original pattern
$\bm{\psi}_{k}{\,\in\,}\Psi$, i.e.,
$\bm{\gamma}_{\ell}{\,\triangleq\,}(m_{1},m_{2})\circ\bm{\psi}_{k}$ for some
$m_{1},m_{2}{\,\in\,}\mathcal{X}$. Then the total gain $W_{s\ell}$ accumulated
over all type-$\ell$ agents from observing (partial) occurrences of
$\bm{\gamma}_{\ell}$ in $\bm{\beta}_{s}$, is given by
$W_{s\ell}{\,\triangleq\,}\sum_{j=1}^{\min(b_{s}-1,L+1)}D_{j}^{(1)}(\bm{\beta}_{s},\bm{\gamma}_{\ell}){\,+\,}\sum_{j=1}^{\min(b_{s}-1,L)}D_{j}^{(2)}(\bm{\beta}_{s},\bm{\gamma}_{\ell})$
with $D_{i}^{(1)}$ and $D_{i}^{(2)}$ defined based on the reward strategy from
Definition 10. First,

$\displaystyle
D_{i}^{(1)}(\bm{\beta}_{s},\bm{\gamma}_{\ell}){\,\triangleq\,}\left(P[m_{1},m_{2}]P[m_{2},\psi_{k,1}]\prod_{j=2}^{i-1}P[\psi_{k,j-1},\psi_{k,j}]\right)^{-1}$

if $\beta_{b_{s}-i}{\,=\,}m_{1}$ and
$\beta_{b_{s}-i+1}{\,=\,}m_{2},\beta_{b_{s}-i+j}{\,=\,}\psi_{k,j-1}$ for all
$j{\,\in\,}\\{2,\cdots,i\\}$; else,
$D_{i}^{(1)}(\bm{\beta}_{s},\bm{\gamma}_{\ell}){\,=\,}0$. Second,

$\displaystyle
D_{i}^{(2)}(\bm{\beta}_{s},\bm{\gamma}_{\ell}){\,\triangleq\,}\left(P[\beta_{b_{s}-i},\psi_{1}]\prod_{j=2}^{i}P[\psi_{k,j-1},\psi_{j}]\right)^{-1}$

if $\beta_{b_{s}-i}{\,\neq\,}m_{2}$ and $\beta_{b_{s}-i+j}{\,=\,}\psi_{j}$ for
all $j{\,\in\,}\\{1,\cdots,i\\}$; else,
$D_{i}^{(2)}(\bm{\beta}_{s},\bm{\gamma}_{\ell})=0$. A gain matrix
$W{\,\in\,}\mathbb{R}^{(K_{I}+K_{L})\times K_{L}}$ is constructed with entries
$W_{s\ell}$ for each pair of $\bm{\beta}_{s}{\,\in\,}\mathcal{S}$ and
$\bm{\gamma}_{\ell}{\,\in\,}\Gamma$.

######  Definition 13 (Cumulative Net Reward).

The expected type-$\ell$ cumulative net reward over all type-$\ell$ agents by
mode-index $\tau$ is defined
$\mathbb{E}[R_{\tau}^{(\ell)}]{\,\triangleq\,}c_{\ell}([\mathbb{P}(\bm{\beta}_{1}),\cdots,\mathbb{P}(\bm{\beta}_{K_{I}+K_{L}})]W_{\cdot,\ell}-\mathbb{E}[\tau])$,
where the $\mathbb{P}(\bm{\beta}_{s})$ are the probabilities from Definition
11 and $W_{\cdot,\ell}$ denotes the $\ell$th column of the gain matrix (see
Definition 12). Correspondingly, the expected cumulative net reward over all
agents by mode-index $\overline{n}$ is defined as
$R_{\overline{n}}\triangleq\sum_{\ell=1}^{K_{L}}R_{\overline{n}}^{(\ell)}$,
and

$\displaystyle\hskip
2.84544pt\mathbb{E}[R_{\tau}]\\!=\\![\mathbb{P}(\bm{\beta}_{1})\cdots\mathbb{P}(\bm{\beta}_{K_{I}+K_{L}})]W{\bf
c}\\!-\\!\left(\sum\limits_{\ell=1}^{K_{L}}c_{\ell}\right)\mathbb{E}[\tau]$
(8)

where ${\bf c}{\,\triangleq\,}[c_{1},\cdots,c_{K_{L}}]^{\top}$ are the initial
rewards (Definition 10).

###  5.2 Solving the Pattern-Occurrence Problem

We are now ready to use our construction to present our main results, which
address the questions in Problem 1.

######  Theorem 1 (Expected Time of Occurrence).

Denote $\tau$ as in Remark 6 with (estimated) current mode $\varphi_{0}$ for
the collection $\Psi$ from Definition 2 and corresponding augmented collection
$\Gamma$. Then

$\displaystyle\mathbb{E}[\tau]=\frac{1}{\sum\limits_{\ell=1}^{K_{L}}c_{\ell}^{*}}\Bigg{[}\Bigg{(}1-\sum\limits_{s=1}^{K_{I}}\mathbb{P}(\bm{\beta}_{s})\Bigg{)}+\sum\limits_{s=1}^{K_{I}}\mathbb{P}(\bm{\beta}_{s})\sum\limits_{\ell=1}^{K_{L}}W_{s\ell}c_{\ell}^{*}\Bigg{]}$
(9)

where $\bm{\gamma_{\ell}}{\,\in\,}\Gamma$,
$\bm{\beta}_{s}{\,\in\,}\mathcal{S}$, $\mathbb{P}(\bm{\beta}_{s})$ is from
Definition 11, $W$ is from Definition 12, and ${\bf
c}^{*}{\,\in\,}\mathbb{R}^{K_{L}}$ is the vector of initial rewards (see
Definition 12) such that $\sum_{\ell=1}^{K_{L}}W_{s\ell}c_{\ell}^{*}{\,=\,}1$
for all $s{\,\in\,}\\{K_{I}{\,+\,}1,\cdots,K_{I}+K_{L}\\}$.

###### Proof.

Because the Markov chain is irreducible and finite-state,
$\mathbb{E}[\tau^{a}_{\ell}]{\,<\,}\infty$, for each $\tau_{\ell}^{a}$ defined
in Remark 5. Note that
$\tau_{k}{\,=\,}\min_{\bm{\gamma}_{\ell}\in\Gamma_{k}}\tau^{a}_{\ell}$, where
$\Gamma_{k}$ is the subset of $\Gamma$ containing augmented patterns
$\bm{\gamma}{\,\triangleq\,}(m_{1},m_{2})\circ\bm{\psi}_{k}$ corresponding to
original pattern $\bm{\psi}_{k}{\,\in\,}\Psi$. We have that
$\tau{\,\triangleq\,}\min_{k}\tau_{k}$, and by Definition 6, we also have
$\mathbb{E}[\tau]{\,<\,}\infty$. By the construction of the gain matrix $W$
and the fact that linear combinations of martingales are martingales, both
$\\{R_{n\wedge\tau^{a}_{\ell}}^{(\ell)}\\}_{n\in\mathbb{N}}$ and
$\\{R_{n\wedge\tau}\\}_{n\in\mathbb{N}}$ are martingales. This implies that
$\mathbb{E}[R_{\tau^{a}_{\ell}}^{(\ell)}]{\,<\,}\infty$ since
$\mathbb{E}[\tau^{a}_{\ell}]{\,<\,}\infty$. Furthermore,
$\mathbb{E}[R_{\tau}]{\,<\,}\infty$ because $\tau{\,\leq\,}\tau^{a}_{\ell}$
for all $\ell$. Define the set
$\Omega_{n}^{(\ell)}{\,\triangleq\,}\\{\omega{\,\in\,}\Omega|n{\,<\,}\tau^{a}_{\ell}\\}$.
By Doob’s martingale convergence theorem and the triangle inequality,
$\lim_{n\to\infty}\int_{\Omega_{n}^{(\ell)}}\lvert
R_{n}^{(\ell)}(\omega)\rvert d\mathbb{P}(\omega)=0$, which implies
$\\{R_{n\wedge\tau^{a}_{\ell}}^{(\ell)}\\}$ is uniformly-integrable over
$\Omega_{n}^{(\ell)}$. Thus, $\\{R_{n\wedge\tau}\\}$ is uniformly-integrable
over
$\Omega_{n}{\,\triangleq\,}\\{\omega{\,\in\,}\Omega{\,|\,}n{\,<\,}\tau\\}{\,\subseteq\,}\cap_{\ell=1}^{K_{L}}\Omega_{n}^{(\ell)}$.
With the above conditions satisfied, we apply the optional stopping theorem to
the stopped process $\\{R_{n\wedge\tau}\\}$, which implies
$\mathbb{E}[R_{\tau}]{\,=\,}\mathbb{E}[R_{0}]$. Note
$\mathbb{E}[R_{0}]{\,=\,}0$ by the construction of Definition 13. After
choosing the initial rewards ${\bf c}^{*}$ as in the theorem statement, and
substituting into (8):

$\displaystyle\mathbb{E}[R_{\tau}]\\!$
$\displaystyle=\\!\sum\limits_{s=1}^{K_{I}}\mathbb{P}(\bm{\beta}_{s})\sum\limits_{\ell=1}^{K_{L}}W_{s\ell}c_{\ell}^{*}\\!+\\!\left(1\\!-\\!\sum\limits_{s=1}^{K_{I}}\mathbb{P}(\bm{\beta}_{s})\right)\\!-\\!\sum\limits_{\ell=1}^{K_{L}}c_{\ell}\mathbb{E}[\tau]$

Rearranging the terms to isolate $\mathbb{E}[\tau]$ yields (9). ∎

This addresses the first question in Problem 1. To address the second
question, we use the following theorem, which also addresses the computation
of $\mathbb{P}(\bm{\beta}_{s})$ for any later-ending string
$\bm{\beta}_{s}{\,\in\,}\mathcal{S}_{L}$ (see Definition 11).

######  Theorem 2 (First-Occurrence Probabilities).

In addition to the setup of Theorem 1, explicitly denote as ending string as
$\bm{\beta}_{s}{\,\triangleq\,}(\beta_{1},\cdots,\beta_{b_{s}}){\,\in\,}\mathcal{S}$
to have length $b_{s}{\,\in\,}\mathbb{N}$. Then the (estimated) first-
occurrence probabilities $\\{q_{k}\\}$ (see Definition 6 and Remark 4) are
given by
$q_{k}{\,=\,}\sum_{\bm{\beta}_{s}\in\mathcal{S}}\mathbb{P}(\bm{\beta}_{s})\mathds{1}\\{\beta_{b_{s}-L+1:b_{s}}{\,=\,}\bm{\psi}_{k}\\}$.

###### Proof.

Rearranging the terms of (8) yields:

$\displaystyle\sum\limits_{s=1}^{K_{I}}\mathbb{P}(\bm{\beta}_{s})\sum\limits_{\ell=1}^{K_{L}}W_{s\ell}c_{\ell}=-\sum\limits_{s=K_{I}+1}^{K_{I}+K_{L}}\mathbb{P}(\bm{\beta}_{s})\sum\limits_{\ell=1}^{K_{L}}W_{s\ell}c_{\ell}+\sum\limits_{\ell=1}^{K_{L}}c_{\ell}\mathbb{E}[\tau]$
(10)

We are given $\mathbb{E}[\tau]$ from Theorem 1, and
$\mathbb{P}(\bm{\beta}_{s})$ can be computed via Definition 11 when
$\bm{\beta}_{s}{\,\in\,}\mathcal{S}_{I}$. For
$s{\,\in\,}\\{K_{I}+1,\cdots,K_{I}+K_{L}\\}$, choose one of $K_{L}$ vectors
${\bf c}\in\\{{\bf e}_{1},\cdots,{\bf e}_{K_{L}}\\}$ (where ${\bf e}_{i}$ is
the $i$th standard basis vector of $\mathbb{R}^{K_{L}}$) to substitute into
(10) and construct $K_{L}$ different equations. Solve the resulting linear
system for the $K_{L}$ unknowns
$\\{\mathbb{P}(\bm{\beta}_{K_{I}+1}),\cdots,\mathbb{P}(\bm{\beta}_{K_{I}+K_{L}})\\}$.
By Definition 6,
$q_{k}{\,\triangleq\,}\mathbb{P}(\tau{\,=\,}\tau_{k}){\,=\,}\sum_{\bm{\beta}_{s}\in\mathcal{S}}\mathbb{P}(\bm{\beta}_{s})\mathbb{P}(\tau{\,=\,}\tau_{k}\,|\,\bm{\beta}_{s})$,
where we denote shorthand $\mathbb{P}(\tau{\,=\,}\tau_{k}\,|\,\bm{\beta}_{s})$
to be the probability of $\bm{\psi}_{k}$ being the first pattern observed at
mode-index $\tau$ given $\bm{\beta}_{s}$ is the ending string which terminated
the mode process in the sense of Definition 9. Clearly,
$\mathbb{P}(\bm{\psi}_{k}\,|\,\bm{\beta}_{s}){\,=\,}1$ if
$\beta_{b_{s}-L+1:b_{s}}{\,=\,}\bm{\psi}_{k}$ holds, otherwise it is $0$. We
thus obtain the desired equation. ∎

######  Remark 7.

In order to fit the closed-form expressions of Theorems 1 and 2 into the
original architecture described throughout Sec. 3, we unsimplify the notation
from Remark 4 and Remark 6 for general time $t{\,\in\,}\mathbb{N}$ and
corresponding mode-index $n{\,\triangleq\,}N[t]$. This yields the original
time-dependent pattern-occurrence quantities desired in Problem 1. Namely,
with estimated current mode $\hat{\varphi}_{n}^{(t)}$ and TPM $\hat{P}^{(t)}$,
the estimated expected minimum occurrence time
$\mathbb{E}[\hat{\tau}_{n}^{(t)}]$ is the $\mathbb{E}[\tau]$ computed from
Theorem 1, while the estimated first occurrence probabilities
$\\{\hat{q}_{k}^{(t)}\\}$ are the $\\{q_{k}\\}$ computed from Theorem 2.

##  6 Control Law Design

In this section, we tie the pattern-occurrence quantities developed in Sec. 5
into our choice of implementation for the Control Law Design component. One
well-known control method that explicitly incorporates predictions is model
predictive control (MPC), and so we use principles similar to MPC to schedule
control policies in advance (see Proposition 1). For the purposes of our
dynamic topology network case study in Sec. 7, we also discuss non-predictive
Control Law Design using the novel system level synthesis approach (Wang et
al., 2018; Anderson et al., 2019), including a topology-robust version (Han,
2020) and a data-driven version (Xue and Matni, 2021; Alonso et al., 2022).

###  6.1 Incorporating Predictions

We implement a table $\mathcal{U}$ that maps patterns of interest to the
optimal control sequences we designed for them in our experiment so far (see
Proposition 2); this also includes explicit state and control trajectories.
This implementation was inspired by episodic memory (Lengyel and Dayan, 2007)
which can be added to learning-based control methods (e.g., reinforcement
learning) to recall specific experiences and their rewards (Blundell et al.,
2016). Our table $\mathcal{U}$ is implemented according to Proposition 2 and
its entries are updated in two ways: 1) the control law is updated in an entry
for an existing pattern, or 2) a new entry is created for a newly-observed
pattern $\bm{\psi}$ at time $t$, where $\bm{\psi}{\,\in\,}\Psi[t{\,+\,}1]$ but
$\bm{\psi}{\,\not\in\,}\Psi[t]$. We describe the control law synthesis and
update procedures in the following Sec. 6.2.

For the prediction component, we specifically recall model predictive control
(MPC). Standard MPC for discrete-time linear dynamics seeks to predict a
future sequence of controls $\\{{\bf u}[t],{\bf u}[t+1],\cdots,{\bf
u}[t+H]\\}$ which minimizes some cost functional at each timestep
$t{\,\in\,}\mathbb{N}$, for some prediction horizon $H{\,\in\,}\mathbb{N}$.
Once the first control input ${\bf u}[t]$ is applied to the system, the
procedure is repeated at the next time $t+1$. Although intuitive,
incorporating both short-term and long-term predictions for online control
have been proven to be beneficial, even when the system to be controlled is
perturbed by either random and adversarial disturbances (Chen et al., 2015);
in Yu et al. (2020), this is demonstrated explicitly with the linear quadratic
regulator. For the concreteness of this paper, we are inspired by the methods
of Park and Kwon (2002) and Lu et al. (2013), which discuss MPC for MJS, and
we extend their approaches to our setting from Sec. 2.

We remark that $H$, like prediction horizon $L$ for the mode process, is a
user-chosen hyperparameter; one reasonable choice could be to make it time-
varying and set it equal to $\Delta T-(t-T_{N[t]})$ at each $t$. Given the
estimated current mode $m{\,\triangleq\,}\hat{\varphi}_{N[t]}^{(t)}$, the cost
function we seek to optimize is the following mode-dependent quadratic cost
function:

$\displaystyle J(t,m)$ $\displaystyle\triangleq\sum\limits_{s=t}^{H}({\bf
x}[s]^{\top}Q(m){\bf x}[s]+{\bf u}[s]^{\top}R(m){\bf u}[s])$
$\displaystyle\hskip 28.45274pt+{\bf x}[H]^{\top}Q_{f}(m){\bf x}[H]$ (11)

The main distinction is that the prediction part of MPC is done on the
estimated mode process instead of the system dynamics. Let
$t{\,\in\,}\mathbb{N}$ and $n{\,\triangleq\,}N[t]$, and suppose the consistent
set narrowing approach of Sec. 3.1 estimates the current mode to be
$\hat{\varphi}_{n}^{(t)}$. Again, by Assumption 1, there are at most $\Delta
T-1$ state and control observations ${\bf x}[T_{n}{\,:\,}t]$ and ${\bf
u}[T_{n}{\,:\,}t]$ associated with each mode $\varphi_{n}$. Thus, for the
control input ${\bf u}[t]=K(t,\hat{\varphi}_{n}^{(t)}){\bf x}[t]$ at time $t$,
the gain $K(t,\hat{\varphi}_{n}^{(t)}){\,\in\,}\mathbb{R}^{n_{x}\times n_{u}}$
associated specifically with mode $\hat{\varphi}_{n}^{(t)}$ can be designed
using standard linear optimal control tools such as LQR minimization.

###  6.2 System Level Synthesis

For the purposes of this paper (especially for our case study in Sec. 7), we
employ the novel system level synthesis (SLS) (Wang et al., 2018; Anderson et
al., 2019) approach for distributed disturbance-rejection in linear discrete-
time network systems with static topologies
$\mathcal{G}{\,\triangleq\,}(\mathcal{V},\mathcal{E})$, expressed as

$\displaystyle{\bf x}[t+1]=A{\bf x}[t]+B{\bf u}[t]+{\bf w}[t]$ (12)

The standard state-feedback control law for systems of this form is given by
${\bf u}[t]{\,=\,}K{\bf x}[t]$ and in $z$-transform expression, the resulting
closed-loop system is given by ${\bf x}{\,=\,}(zI-A-BK)^{-1}{\bf w}$. However,
for large-scale systems (i.e., large-dimensional matrices $A$ and $B$),
optimizing over the transfer function $(zI-A-BK)^{-1}$ by solving for $K$ is
difficult. Thus, a key feature of SLS is that it reparametrizes the control
problem: instead of designing just the open-loop feedback gain $K$, SLS
designs for the entire closed-loop system via response maps
$\bm{\Phi}{\,\triangleq\,}\\{\bm{\Phi}_{x},\bm{\Phi}_{u}\\}$ such that ${\bf
x}[0{\,:\,}t]{\,=\,}\bm{\Phi}_{x}{\bf w}[0{\,:\,}t]$ and ${\bf
u}[0{\,:\,}t]{\,=\,}\bm{\Phi}_{u}{\bf w}[0{\,:\,}t]$, where ${\bf w}[t]$ is an
additive external disturbance.

######  Lemma 1.

For the linear, discrete-time static dynamics (12), the following are true.
First, the affine subspace described by

$\displaystyle\begin{bmatrix}I-Z\hat{A}&-Z\hat{B}\end{bmatrix}\begin{bmatrix}\bm{\Phi}_{x}\\\
\bm{\Phi}_{u}\end{bmatrix}=I$ (13)

parametrizes all possible system responses $\bm{\Phi}$, where
$\hat{A}\triangleq\text{blkdiag}(A,\cdots,A,\textbf{0}){\,\in\,}\mathbb{R}^{Hn_{x}\times
Hn_{x}}$, $\hat{B}$ is defined similarly, $Z$ is the block-downshift operator,
$n_{x}{\,\in\,}\mathbb{N}$ is the state dimension, and $H{\,\in\,}\mathbb{N}$
is a chosen finite horizon over which control is performed. Second, for any
$\bm{\Phi}$ which satisfies the condition in (13), the feedback gain
$K{\,\triangleq\,}\bm{\Phi}_{u}\bm{\Phi}_{x}^{-1}$ achieves the desired
internally-stabilizing system response.

The state-feedback controller is then implemented with:

$\displaystyle\hat{{\bf x}}[t]$
$\displaystyle=\sum\limits_{s=2}^{H}\Phi_{x}[s]\hat{{\bf w}}[t+1-s],\hskip
2.84544pt\hat{{\bf w}}[t]={\bf x}[t]-\hat{{\bf x}}[t]$ $\displaystyle{\bf
u}[t]$ $\displaystyle=\sum\limits_{s=1}^{H}\Phi_{u}[s]\hat{{\bf w}}[t+1-s]$
(14)

where $\hat{{\bf w}}$ is the controller’s internal state and $\hat{{\bf x}}$
is the controller’s estimate of the state. This form also makes SLS more
suitable for distributed and localized control law design in large-scale
linear systems, and so $\bm{\Phi}$ is often implemented as
$\bm{\Phi}^{(i)}{\,\triangleq\,}\\{\Phi_{x}^{(i)}[s],\Phi_{u}^{(i)}[s]\\}$ for
each node $i{\,\in\,}\mathcal{V}$ and its local subsystem $\mathcal{L}_{i,h}$.
Here, $s{\,\in\,}\\{1,\cdots,H\\}$ is the index of the spectral component,
$\mathcal{L}_{i,h}$ is the set of all $j{\,\in\,}\mathcal{V}$ which is within
$h{\,\in\,}\mathbb{N}$ edges away from $i$, and $h$ is some number of hops.
Both time horizon $H$ and number of neighboring hops $h$ are parameters chosen
by design based on properties such as the scale and topology of $\mathcal{G}$.

We can also extend SLS to account for dynamic topologies
$\mathcal{G}(m){\,\triangleq\,}(\mathcal{V},\mathcal{E}(m))$ for
$m{\,\in\,}\mathbb{N}$ representing the index of the topology; this was done
in Han (2020). Let
$\bm{\Phi}_{m}^{(i,t)}{\,\triangleq\,}\\{\Phi_{x,m}^{(i,t)}[s],\Phi_{u,m}^{(i,t)}[s]\\}$
define the $i$th local response map $\bm{\Phi}^{(i)}$ which is created
specifically for topology $m{\,\in\,}\\{1,\cdots,M\\}$. As we demonstrate for
our case study in Sec. 7, the mode in our original dynamics (1) corresponds to
the index of the current topology the system is in. Topology-robust SLS
essentially attempts to design a single $\\{\Phi_{x},\Phi_{u}\\}$ response
that can simultaneously stabilize multiple topologies (i.e., distinct $A$
matrices). Conditions for simultaneous stabilization for a collection of
discrete-time LTI systems have been studied extensively in past literature:
some results (e.g., Blondel et al. (1993)) express the condition by ensuring
that the closed-loop transfer function between every possible plant-controller
pair does not have any pole-zero cancellations, while others (e.g., Cao et al.
(1999)) derive conditions based on the algebraic Riccati equation. To keep our
discussion focused, we do not state these conditions here (see Remark 3).

To be able to use PLP with the SLS approach, we require a formulation of SLS
which is driven by data. Towards that end, we leverage data-driven SLS (Xue
and Matni, 2021; Alonso et al., 2022), which extends traditional SLS using a
characterization based on Willems’ fundamental lemma (Willems and Polderman,
1997), which parametrizes state and input trajectories based on past
trajectories under the conditions of persistence of excitation. Define the
Hankel matrix

$\displaystyle\hat{H}_{r}({\bf x}[0:H]){\,\triangleq\,}\begin{bmatrix}{\bf
x}[0]&{\bf x}[1]&\cdots&{\bf x}[H-r]\\\ {\bf x}[1]&{\bf x}[2]&\cdots&{\bf
x}[H-r+1]\\\ \vdots&\vdots&\ddots&\vdots\\\ {\bf x}[r-1]&{\bf
x}[r]&\cdots&{\bf x}[H-1]\end{bmatrix}$

for finite time horizon $H$ and some $r{\,\in\,}\mathbb{N}$. We say the
finite-horizon state trajectory ${\bf x}[0:H]$ is persistently-exciting of
order $r$ if $\hat{H}_{r}({\bf x}[0:H])$ is full rank. In the data-driven
formulation of SLS, the achievable subspace described by (13) can be
equivalently written as the set

$\displaystyle\left\\{\begin{bmatrix}\hat{H}_{H}({\bf x}[0{\,:\,}H])\\\
\hat{H}_{H}({\bf u}[0{\,:\,}H])\end{bmatrix}G\hskip 2.84544pt\bigg{|}\hskip
2.84544ptG\text{ s.t. }\hat{H}_{1}({\bf x}[0{\,:\,}H])G=I\right\\}$ (15)

Now, let $n{\,\in\,}\mathbb{N}$ and $n^{\prime}{\,\in\,}\mathbb{N}$,
$n^{\prime}{\,>\,}n$, be such that at times $T_{n}$ and $T_{n^{\prime}}$, the
system (1) have switched to the same mode $m{\,\in\,}\mathcal{X}$. For our PLP
approach, the state/control trajectories $\\{{\bf
x}[T_{n-1}{\,:\,}T_{n}-1],{\bf u}[T_{n-1}{\,:\,}T_{n}-1]\\}$ and $\\{{\bf
x}[T_{n^{\prime}-1}{\,:\,}T_{n^{\prime}}-1],{\bf
u}[T_{n^{\prime}-1}{\,:\,}T_{n^{\prime}}-1]\\}$ can be collectively used to
design the optimal control law for mode $m$, i.e., we use horizon
$T_{n-1}{\,:\,}T_{n}-1$ in place of $[0{\,:\,}H]$ in (15). To implement
memory, we store (in $\mathcal{U}$) previous trajectories of the system
corresponding to the same mode, and continue to append to it as the simulation
progresses. To apply Proposition 1, SLS is run more than once to compute a new
$\bm{\Phi}$ for every new estimated mode
$m{\,\triangleq\,}\hat{\varphi}_{n}^{(t)}$, hence the dependence of
$\bm{\Phi}_{m}^{(i,t)}$ on time $t{\,\in\,}\mathbb{N}$. By Proposition 2, the
$\bm{\Phi}_{m}^{(i,t)}$ are stored and updated over time in the table
$\mathcal{U}$, then used to compute ${\bf u}[t]$ via (6.2).

##  7 Case Study: Topology-Switching Network

Controlling networks that undergo parametric and/or topological changes (e.g.,
due to faults or connectivity changes of mobile agents) is an important and
widely-studied problem in large-scale networked systems. In the recent
literature, an adaptive, consensus-based control scheme for complex networks
with time-varying, switching network topology was discussed in Chung et al.
(2013). Distributed target-detection and tracking using a dynamic sensor
network was studied in Bandyopadhyay and Chung (2018), while Saboori and
Khorasani (2015) described fault-tolerance against actuator failures in a
multiagent system connected by a switching topology network.

For the purposes of this paper, we demonstrate the proposed controller
architecture to the following extension of (1), which switches among a finite
number of different topologies
$\mathcal{G}(m)\triangleq(\mathcal{V},\mathcal{E}(m)),m\in\\{1,\cdots,M\\},M{\,\in\,}\mathbb{N}$.

$\displaystyle{\bf x}_{i}[t+1]$ $\displaystyle=A_{ii}(\xi_{N[t]}){\bf
x}_{i}[t]$
$\displaystyle+\sum\limits_{j\in\mathcal{N}_{i}(\xi_{N[t]})}A_{ij}(\xi_{N[t]}){\bf
x}_{j}[t]+B_{i}{\bf u}[t]+{\bf w}_{i}[t]$ (16)

Here, $n_{s}{\,\triangleq\,}\lvert\mathcal{V}\rvert$,
$i{\,\in\,}\\{1,\cdots,n_{s}\\}$, the neighboring nodes of subsystem $i$ are
$\mathcal{N}_{i}(m){\,\triangleq\,}\\{j{\,\in\,}\mathcal{V}{\,:\,}(i,j){\,\in\,}\mathcal{E}(m)\\}$,
and $A(m)\triangleq[A_{ij}(m)]{\,\in\,}\mathbb{R}^{n_{x}\times n_{x}}$ for
each topology $m{\,\in\,}\\{1,\cdots,M\\}$. The assumptions from Sec. 2 still
hold, and the mode process $\\{\xi_{n}\\}$ is the index of the current
topology at time $t{\,\in\,}\mathbb{N}$ with $N[t]$ being the number of
topology changes made by time $t$.

###  7.1 Experiment Setup

The overall control objective is to minimize the mode-dependent quadratic cost
function (6.1) subject to constraints imposed by various implementations of
SLS from Sec. 6.2. Namely, we consider three versions of the controller
architecture Fig. 1; a visual distinction among the three is shown in Fig. 5.

  * •

Baseline [First row of Fig. 5]: here, Fig. 1 is implemented only using Mode
Process ID; both PLP and MPC are not used. The Control Law Design component is
implemented with the basic SLS approach from Sec. 6.2. We minimize the cost
(6.1) subject to the achievability constraint described by (13) and the
locality constraint described with the sets
$\\{\mathcal{L}_{i,h}\\}_{i\in\mathcal{V}}$. Because the topology changes over
time and basic SLS is not designed for time-varying topologies, this requires
the optimization to be solved multiple times.

  * •

Topology-Robust [Second row of Fig. 5]: we have the same architecture as
above, but SLS is replaced with the method of Han (2020), an extension of SLS
to network dynamics under time-varying topological changes. A single common
control law $\bm{\Phi}^{(i,t)}$ is designed for all consistent modes in
$\mathcal{C}[t]$, and this common law is used until time $t^{*}{\,>\,}t$ when
$\lvert\mathcal{C}[t^{*}]\rvert{\,=\,}1$, after which standard SLS is used.

  * •

PLP [Third row of Fig. 5]: we combine the original architecture proposed by
Fig. 1 with the extended SLS approach described in Sec. 6.2. We minimize the
cost (6.1) subject to the data-driven achievability constraint described by
(15) and the locality constraint described with the sets
$\\{\mathcal{L}_{i,h}\\}_{i\in\mathcal{V}}$. Given pattern collection
$\Psi[t]$ at time $t{\,\in\,}\mathbb{N}$ and mode-index
$n{\,\triangleq\,}N[t]$, if
$\bm{\psi}{\,\triangleq\,}(\psi_{1},\cdots,\psi_{L}){\,\in\,}\Psi[t]$ is
expected to occur at mode-index
$n{\,+\,}\mathbb{E}[\hat{\tau}_{n}^{(t)}]{\,\in\,}\mathbb{N}$, the control law
for node $i{\,\in\,}\mathcal{V}$ is scheduled to be $\bm{\Phi}_{m}^{(i,s)}$,
where $m{\,=\,}\psi_{1}$ and
$s{\,\in\,}[T_{n+\mathbb{E}[\hat{\tau}_{n}^{(t)}]},t^{*})$, where $T_{n}$ is
defined in Assumption 1 and $t^{*}$ is the time after
$T_{n+\mathbb{E}[\hat{\tau}_{n}^{(t)}]}$ when
$\lvert\mathcal{C}[t^{*}]\rvert{\,=\,}1$. For times
$s{\,\in\,}[t,T_{n+\mathbb{E}[\hat{\tau}_{n}^{(t)}]})$ where a prediction is
not available, we revert to the baseline controller.

Figure 5: The time-varying control law for each of the three versions of the
controller architecture, designed based on the estimated mode
$\hat{\varphi}_{n}^{(t)}$ and the consistent set $\mathcal{C}[t]$. Each
horizontal bar represents a time duration of length $\Delta T$. The baseline
uses the previous law until the consistent set converges to a singleton set
(white sub-bars). Topology-Robust is able to control multiple modes
simultaneously, so it uses a robust law (red sub-bars) until the convergence.
PLP (future horizon $L{\,=\,}3$) uses the law corresponding to the predicted
next mode (blue sub-bars) until convergence; note that when the mode in the
converged consistent set is equivalent to the predicted next mode, the control
policy need not be changed.

The three architectures are each tested on two specific network systems of the
form given in (7). For both systems, the specific $A$ and $B$ matrices in (7)
are the linearized discrete-time power grid dynamics given in Sec. 5 of Han
(2020), which we do not repeat here for the sake of brevity.

  * •

(Small-Scale) Hexagon System: the network system (7) consists of a hexagonal
arrangement of $n_{s}{\,=\,}7$ nodes and $M{\,=\,}8$ topologies (see Fig. 6).
When PLP is included, the collection of patterns $\Psi[t]$ is constructed with
equality in (4); hence, Problem 1 become easy to solve – every ending string
in $\mathcal{S}$ is an initial-ending string,
$\mathbb{E}[\hat{\tau}_{n}^{(t)}]{\,=\,}L$ for each $t{\,\in\,}\mathbb{N}$,
$n{\,\triangleq\,}N[t]$, and determining
$\text{argmax}_{k}\\{\hat{q}_{k}^{(t)}\\}$ reduces to a maximum likelihood
problem.

  * •

(Large-Scale) Rectangular Grid System: the network system (7) consists of a
$10\times 10$ rectangular grid arrangement of $n_{s}{\,=\,}100$ nodes and
$M{\,=\,}20$ topologies (see Fig. 7). The true TPM is a $M\times M$ stochastic
matrix with no self-transitions. When PLP is included, the collection
$\Psi[t]$ is constructed with strict subset in (4), which means the formulas
from Theorems 1 and 2 must be used to solve Problem 1.

Figure 6: [Left] The different possible topologies of the Hexagon System.
[Right] The underlying Markov chain for topology transitions. Figure 7: The
different possible topologies of the $10{\,\times\,}10$ Rectangular Grid
System.

Even though the Control Law Design component of all three architectures is
localized and distributed by the nature of SLS, we initially assume Mode
Process ID and PLP are centralized. This is reasonable under Assumption 1,
which imposes that communications among subsystems are much faster compared to
the switching of the topologies. This is often the case in fault-tolerance for
large-scale network applications such as the power grid and the internet,
where faults are expected to occur rarely. Furthermore, in Sec. 7.3, we
introduce the implementation of localized, distributed Mode Process ID and
PLP. For simplification of terminology in this section only, we overload the
terminology “PLP” to refer to both the controller with PLP (third row of Fig.
5) and a component of the controller architecture in Fig. 1 that leverages
other algorithms, with the understanding that PLP truly refers to the latter.

###  7.2 Tradeoff Comparison Results

Each simulation is run by applying one of the three controller architectures
to one of the two network systems. We run a total of $20$ Monte-Carlo
experiment trials and each trial is run for $T_{\text{sim}}{\,=\,}400$
timesteps with $\Delta T{\,=\,}10$. The PLP architecture also uses a future
horizon of $L{\,=\,}3$. A sample trajectory of the states and control versus
time for all three architectures is shown in Fig. 8 for the hexagon system; we
reduce the time horizon to $80$ timesteps for this figure only so that there
is better clarity in distinguishing the lines. Because the objective is the
reject external disturbances, the state values waver around the zero line.
Moreover, under Topology-Robust, the state has the smallest oscillations
around zero (green), followed by PLP (red), and finally the baseline (blue). A
sample evolution of the consistent set narrowing approach applied for Mode
Process ID is also shown in Fig. 9 for the baseline and PLP architectures;
again, we plot for a shorter horizon of time (120 timesteps) for easier
visibility. The PLP architecture manages to successfully narrow the consistent
set down to a singleton within the $\Delta T$ time interval more often than
the baseline, and consequently also manages to track the true mode more
precisely.

The comparisons among the different scenarios are performed by evaluating one
of the following four performance metrics. First, to measure the control
effort, an LQR-like cost (17a) is averaged over the simulation time
$T_{\text{sim}}$. Second, to measure the disturbance-rejection performance, we
consider the time-average error norm (17b). Third, we measure the proportion
(17c) of the simulation duration in which the matching control law is used to
control the current topology. Here, if the true mode is given by $\varphi_{n}$
at time $t$, we say that the matching control law
$\\{\bm{\Phi}_{m}^{(i,t)}{\,:\,}i\in\mathcal{V}\\}$ is used if
$m{\,\triangleq\,}\hat{\varphi}_{n}^{(t)}{\,=\,}\varphi_{n}$. Fourth, the
total runtime is recorded.

$\displaystyle\hskip
28.45274pt\frac{1}{T_{\text{sim}}}\sum\limits_{t=1}^{T_{\text{sim}}}{\bf
x}[t]^{\top}I_{n_{x}}{\bf x}[t]+{\bf u}[t]^{\top}I_{n_{u}}{\bf u}[t]$ (17a)
$\displaystyle\hskip
28.45274pt\frac{1}{T_{\text{sim}}}\sum\limits_{t=1}^{T_{\text{sim}}}\left\lVert{\bf
x}[t]\right\rVert_{2}$ (17b) $\displaystyle\hskip
28.45274pt\frac{1}{T_{\text{sim}}}\sum\limits_{t=1}^{T_{\text{sim}}}\mathds{1}\\{\hat{\varphi}_{n}^{(t)}=\varphi_{n}\\}$
(17c)

where $I_{n_{x}},I_{n_{u}}$ are identity matrices with appropriate dimensions.

The metrics (17) are further averaged over $20$ Monte-Carlo simulations with
varying initial condition ${\bf x}_{0}$, noise process ${\bf w}[t]$, and true
realization $\\{\varphi_{n}\\}$ of the mode process $\\{\xi_{n}\\}$. The
results are tabulated in Table 2 with the three architecture names
abbreviated: ‘Base’ as the baseline, and ‘TR’ as Topology-Robust. The
proportion of time the matching control law is irrelevant for Topology-Robust
because it computes a single law to be used for multiple topologies, hence the
‘–’ entries. We also plot a sample evolution of $\left\lVert
P{\,-\,}\hat{P}^{(t)}\right\rVert$ for one Monte-Carlo trial in Fig. 10, where
the norm taken is the Frobenius norm. Because $\hat{P}^{(0)}$ begins with
uniform probabilities in the nonzero positions, there are some variations in
the norm difference, but overall, the curve decreases with time, indicating
convergence to within a small error ball of the true TPM. This also allows for
the pattern-occurrence quantities to be solved more accurately, which improves
the prediction performance of PLP. As Table 2 shows, this also enables better
controller performance (LQR Cost and Error Norm) of PLP over the other two
architectures.

Figure 8: States and control versus time for one Monte-Carlo trial in the
hexagon system. We abbreviate the baseline controller as ‘Base’, and Topology-
Robust as ‘TR’.  Figure 9: Modes versus time for one Monte-Carlo trial of the
hexagon system. In the bottom subfigure, black vertical lines indicate
intervals of length $\Delta T$.  Figure 10: Frobenius norm of the difference
between the true TPM $P$ and estimated TPM $\hat{P}^{(t)}$ versus time for one
Monte-Carlo trial of the hexagon system.

The values in both sub-rows of the ‘LQR Cost’ row in Table 2 suggest that the
time-average LQR cost of all three controller architectures increase as the
scale of the system gets larger. This is expected because the same values of
horizon $H$ and number of hops $h$ (defined in Sec. 6.2) were chosen for the
SLS implementation of both systems. In practice, $H$ and $h$ must be adjusted
as the scale of the system changes, but for fairer comparison we use the same
values for both the hexagon and grid systems. Furthermore, assuming a small
margin of error, Topology-Robust should theoretically stabilize the system
better than the baseline at the expense of increased control effort because
Topology-Robust uses a single common law is for multiple different modes. This
can be validated empirically by the entries in the ‘LQR Cost’ and ‘Error Norm’
rows, and is also supported by Fig. 8, where the state’s oscillations around
the zero line are the largest in magnitude with the baseline and the least
with Topology-Robust.

Metric / Controller | Base | TR | PLP
---|---|---|---
LQR Cost | $36.4537$ | $42.5596$ | $34.7242$
| $445.8137$ | $472.1195$ | $442.1264$
Error Norm | $2.2146$ | $1.5546$ | $1.5236$
| $6.1294$ | $5.9453$ | $5.8244$
Prop. Match | $0.4304$ | – | $0.615$
| $0.1533$ | – | $0.16$
Runtime | $11.8314$ | $67.2254$ | $2.2689$
| $101.3741$ | X | $38.5824$
Table 2:  The average performance metrics [row] over $20$ Monte-Carlo
simulations of $T_{\text{sim}}{\,=\,}400$ timesteps, for each pair of
controller architecture [column]. In each cell, the top value is recorded for
the hexagon system and the bottom is for the grid system. For space, we
abbreviate ‘Base’ as the baseline controller, and ‘TR’ as Topology-Robust.

More interestingly, the PLP architecture manages to balance the performance
metrics better compared to the the other architectures: LQR cost similar to
the baseline architecture, error norm similar to the Topology-Robust
architecture, and runtime faster than either the baseline or the topology-
robust extension. The improved runtime comes from the PLP component’s ability
to refrain from recomputing parts of the original SLS optimization by
preserving the control inputs of previously-observed topologies and
state/control trajectories (see Proposition 2). Moreover, the ability of PLP
to predict the expected occurrence times of future mode patterns allows for
the scheduling of SLS controllers in advance (see Proposition 1); as seen in
Fig. 5, this improves the error norm when Pattern-Learning manages to predict
the future mode correctly. The ‘Prop Match’ row of Table 2 shows that this is
indeed the case: the PLP architecture consistently uses the matching control
law more often than the baseline regardless of network system. This is
expected since PLP can be viewed as an additional mode estimation algorithm,
and so the estimate $\hat{\varphi}_{n}^{(t)}$ is on average better with PLP
than without. In general, this suggests that appending PLP to a baseline
controller that is neither predictive nor robust to time-varying topologies
could be used as an alternative to Topology-Robust, especially in complex
systems where simultaneous stabilization isn’t possible or is expensive.

We remark that the difference in the construction of the pattern collection
$\Psi[t]$ in the hexagon system versus the grid system also has a role in the
relationship among the performance metrics, especially in the error-norm
performance and the proportion of time the matching control law is used.
Recall that for the hexagon system, $\Psi[t]$ is created by accumulating every
feasible mode sequence of length $L$, which implies
$\mathbb{E}[\hat{\tau}_{n}^{(t)}]{\,=\,}L$. In contrast, for the grid system,
a random subset of feasible mode sequences is chosen per time $t$, and so the
formulas from Theorems 1 and 2 were used to solve Problem 1. In the PLP column
of the ‘Prop. Match’ row, we see the matching control law is used less often
in the grid system than the hexagon system, which is expected since
$\mathbb{E}[\hat{\tau}_{n}^{(t)}]{\,\geq\,}L$ for the grid system and
predictions for a longer horizon of mode-indices become less accurate. Thus,
increasing the number of patterns in the pattern collection decreases the
expected minimum occurrence time, which yields more accurate estimates of
future modes. The Base and PLP columns in the ‘Error Norm’ row suggest that
better predictions enable better disturbance-rejection; this implies that PLP
will more closely resemble the error norm of the baseline when less patterns
are included in $\Psi[t]$.

###  7.3 Localized Pattern-Learning and Prediction

Table 2 shows that performance deteriorates with larger scale, and this can be
attributed to the fact that both Pattern-Learning and Mode Process ID are
implemented in a centralized fashion, which conflicts with the localized,
distributed nature of SLS. We now briefly discuss an extension of PLP to a
localized, distributed implementation of PLP. Since the previous section
already compared the performance of PLP to those of the controllers without
PLP, we focus our discussion here on how the localized implementation of PLP
compares to the centralized version.

Let current time be $t{\,\in\,}\mathbb{N}$ and $n{\,\triangleq\,}N[t]$. Based
on information from its own local subsystem (7), each node
$i{\,\in\,}\mathcal{V}$ stores and updates three objects: a) its own estimates
of the current mode $\hat{\varphi}_{n}^{(i,t)}$ and TPM $\hat{P}^{(i,t)}$
(computed via Sec. 3.1), b) its own estimates of the pattern-occurrence
quantities $\mathbb{E}[\hat{\tau}^{(i,t)}]$,
$\\{\hat{q}^{(i,t)}_{k}\\}_{k=1}^{K}$ (computed via Sec. 3.2 and 5.2), and c)
its own pattern collection $\Psi^{(i)}[t]$ and pattern-to-control law table
$\mathcal{U}^{(i)}$ (see Sec. 3.3). Each node $i{\,\in\,}\mathcal{V}$ employs
the consistent set narrowing approach of (7) to update its own set
$\mathcal{C}^{(i)}[t]$ of consistent topologies over time $t$. Each subsystem
$i{\,\in\,}\mathcal{V}$ then extracts $\hat{\varphi}_{n}^{(i,t)}$,
$\mathcal{C}^{(i)}[t]$, and estimates $\hat{P}^{(i,t)}$ by empirically
counting the proportion of transitions across the entire estimated past
history $\hat{\varphi}_{0:n}^{(i,t)}$. For the TPMs, we also implement
consensus averaging of the estimates to neighboring subsystems that are one
link away, similar to the method of Sec. 4 in Han (2020). Overall, the key
distinction is that we add an additional enumeration $i{\,\in\,}\mathcal{V}$
to the usual sets, tables, and estimated quantities from Sec. 4 and Sec. 5 to
emphasize that each subsystem maintains local estimates of everything.

Figure 11: [Top] The evolution of $\mathbb{E}[\hat{\tau}^{(i,t)}]$ over time
for subsystems $i{\,\in\,}\\{1,4,6\\}$. [Bottom] The evolution over time of
the Frobenuis norm of the difference between $P$ and $\hat{P}^{(i,t)}$ for
subsystems $i{\,\in\,}\\{2,4,6\\}$.

The estimated pattern-occurrence quantities for this localized extension of
PLP applied to the hexagon system are shown in Fig. 11. To demonstrate the
evolution of the pattern-occurrence quantities over time, each subsystem $i$’s
pattern collection $\Psi^{(i)}[t]$ is chosen to contain more than half of the
full combinatorial set of feasible length-$L$ mode sequences initially
considered in Sec. 7.2, such that the true value of
$\mathbb{E}[\hat{\tau}^{(i,t)}]$ is $5.83328$ via Theorem 1. The evolution of
the estimated minimum occurrence time $\mathbb{E}[\hat{\tau}^{(i,t)}]$ over
$t$ is shown at the top, while the Frobenius norm difference
$\|P-\hat{P}^{(i,t)}\|$ of the TPM estimate is shown at the bottom. We use
varying groups of subsystems for these figures in order to demonstrate the
locality property.

Note in Fig. 11, that as time increases, the estimates
$\mathbb{E}[\hat{\tau}^{(i,t)}]$ of tend to converge towards the true value
$5.83328$ as more of the TPM gets learned. The piecewise nature arises because
the pattern collection $\Psi^{(i)}[t]$ may change over time, which in turn
changes each subsystem’s estimate of the expected minimum occurrence time. At
the bottom of Fig. 11, the matrix norm difference between the true and
estimated TPMs for each of the three subsystems decreases over time, which is
expected as each subsystem gathers more data to learn the true transition
probabilities of $P$. Compared to the centralized TPM estimate evolution over
time (Fig. 10) there is more rapid variation in each subsystem’s estimate in
the bottom figure of Fig. 11; this could be attributed to the consensus
averaging among the subsystems. Viewing topologies at a local level can make
the modes look similar to one another, and so a localized implementation of
consistent set narrowing may perform worse than the centralized
implementation. This is a well-known tradeoff between centralized and
distributed control: for more efficient computation, we are trading
performance optimality.

##  8 Conclusion

Pattern-learning for prediction (PLP) learns patterns in the behavior of
stochastic uncertain systems to make controller design efficient by memorizing
patterns to prevent the re-computation of the control laws associated with
previously-occurred patterns (see Proposition 2) and by scheduling of control
laws associated with patterns that may occur in the future (see Proposition
1). In this paper, we aimed to demonstrate the advantages of including PLP in
an otherwise straightforward controller architecture (which borrows techniques
from system identification and predictive control) for a class of linear MJS
whose underlying mode-switching dynamics are unknown; here, the aforementioned
patterns are recurrent finite-length sequences of modes which arise in the
MJS. Our controller architecture consists of three parts. First, Mode Process
ID (Sec. 3.1 and 4) identifies the unknown statistics of the mode process.
Second, PLP (Sec. 3.2 and 5) uses the estimated statistics of the mode process
to compute the pattern-occurrence quantities from Problem 1: the expected
minimum occurrence time of any pattern from a user-defined pattern collection,
and the probability of a pattern being the first to occur among the
collection. The computation of the pattern-occurrence quantities uses
martingale methods from the literature with two key extensions that make it
more applicable to the real-world: 1) the distribution of the mode process is
unknown, and 2) the mode process is not observable; closed-form expressions of
the quantities are derived in Theorems 1 and 2. Third, Control Law Design
(Sec. 3.3 and 6) computes the optimal control action corresponding to each
pattern when it first occurs. We implement PLP on a fault-tolerant controller
of a network with dynamic topology by integrating the pattern-occurrence
quantities into MPC and using variations of SLS (Sec. 6.2) for the Control Law
Design component. We provide an empirical comparison study of its performance
against a baseline controller and a topology-robust extension of the baseline.
Because PLP can be viewed as an additional mode estimation algorithm, it
enables the estimated mode to match the true mode more often, although this is
mainly possible for an optimal choice of pattern collection. Compared to the
baseline, PLP is able to achieve better disturbance-rejection at reduced
computation time, redundancy, and control cost, which suggests its potential
to be used in place of a robust controller for more complex applications where
designing for robustness is expensive. The merit of our work can be summarized
as follows: computation-efficient control design for stochastic systems with
uncertain dynamics can be performed by learning patterns in the system’s
behavior, which eliminates redundancy by storing past patterns into memory and
predicting the future occurrence of patterns.

## ACKNOWLEDGMENTS

The authors would like to thank John Brader and Benjamen Bycroft of the
Aerospace Corporation for their technical inputs.

## References

  * A. Cuzzola et al. (2002) A. Cuzzola, F., C. Geromel, J., Morari, M., 2002.  An improved approach for constrained robust model predictive control.  Automatica 38, 1183–1189.
  * Alessandri et al. (2005) Alessandri, A., Baglietto, M., Battistelli, G., 2005.  Receding-horizon estimation for switching discrete-time linear systems.  IEEE Transactions on Automatic Control 50, 1736 – 1748.
  * Alonso et al. (2022) Alonso, C.A., Yang, F., Matni, N., 2022.  Data-driven distributed and localized model predictive control.  IEEE Open Journal of Control Systems 1, 29–40.
  * Anderson et al. (2019) Anderson, J., Doyle, J.C., Low, S.H., Matni, N., 2019\.  System level synthesis.  Annual Reviews in Control 47, 364–393.
  * Baglietto et al. (2007) Baglietto, M., Battistelli, G., Scardovi, L., 2007.  Active mode observability of switching linear systems.  Automatica 43, 1442–1449.
  * Bandyopadhyay and Chung (2018) Bandyopadhyay, S., Chung, S.J., 2018\.  Distributed bayesian filtering using logarithmic opinion pool for dynamic sensor networks.  Automatica 97, 7–17.
  * Battaglia et al. (2018) Battaglia, P.W., Hamrick, J.B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V.F., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., Gülçehre, Ç., Song, H.F., Ballard, A.J., Gilmer, J., Dahl, G.E., Vaswani, A., Allen, K.R., Nash, C., Langston, V., Dyer, C., Heess, N., Wierstra, D., Kohli, P., Botvinick, M.M., Vinyals, O., Li, Y., Pascanu, R., 2018.  Relational inductive biases, deep learning, and graph networks.  ArXiv preprint, arXiv:1806.01261 .
  * Blondel et al. (1993) Blondel, V., Campion, G., Gevers, M., 1993.  A sufficient condition for simultaneous stabilization.  IEEE Transactions on Automatic Control 38, 1264–1266.
  * Blundell et al. (2016) Blundell, C., Uria, B., Pritzel, A., Li, Y., Ruderman, A., Leibo, J.Z., Rae, J., Wierstra, D., Hassabis, D., 2016.  Model-Free Episodic Control.  ArXiv preprint, arXiv:1606.04460 .
  * Boon and van Leeuwaarden (2016) Boon, M., van Leeuwaarden, J., 2016\.  Networks of fixed-cycle intersections.  ArXiv preprint, arXiv:1611.02947 .
  * Botvinick et al. (2019) Botvinick, M., Ritter, S., Wang, J.X., Kurth-Nelson, Z., Blundell, C., Hassabis, D., 2019\.  Reinforcement Learning, Fast and Slow.  Trends in Cognitive Sciences 23, 408–422.
  * Cao et al. (1999) Cao, Y.Y., Sun, Y.X., Lam, J., 1999.  Simultaneous stabilization via static output feedback and state feedback.  IEEE Transactions on Automatic Control 44, 1277–1282.
  * Chen et al. (2015) Chen, N., Agarwal, A., Wierman, A., Barman, S., Andrew, L.L., 2015.  Online convex optimization using predictions.  SIGMETRICS Perform. Eval. Rev. 43, 191–204.
  * Chen and Liu (2017) Chen, P., Liu, X., 2017.  Repetitive learning control for a class of partially linearizable uncertain nonlinear systems.  Automatica 85, 397–404.
  * Cho and Lim (1998) Cho, K.H., Lim, J.T., 1998.  Synthesis of fault-tolerant supervisor for automated manufacturing systems: a case study on photolithographic process.  IEEE Transactions on Robotics and Automation 14, 348–351.
  * Chung et al. (2013) Chung, S.J., Bandyopadhyay, S., Chang, I., Hadaegh, F.Y., 2013\.  Phase synchronization control of complex networks of Lagrangian systems on adaptive digraphs.  Automatica 49, 1148–1161.
  * Costa et al. (2015) Costa, O.L.d.V., Fragoso, M.D., Todorov, M.G., 2015.  A detector-based approach for the $h_{2}$ control of markov jump linear systems with partial information.  IEEE Transactions on Automatic Control 60, 1219–1234.
  * Cui et al. (2020) Cui, Z., Henrickson, K., Ke, R., Wang, Y., 2020.  Traffic graph convolutional recurrent neural network: A deep learning framework for network-scale traffic learning and forecasting.  IEEE Transactions on Intelligent Transportation Systems 21, 4883–4894.
  * Dean et al. (2019) Dean, S., Tu, S., Matni, N., Recht, B., 2019.  Safely learning to control the constrained linear quadratic regulator, in: 2019 American Control Conference (ACC), pp. 5582–5588.
  * Doyle (1978) Doyle, J., 1978.  Guaranteed margins for LQG regulators.  IEEE Transactions on Automatic Control 23, 756–757.
  * Doyle (1982) Doyle, J., 1982.  Analysis of feedback systems with structured uncertainties.  IEE Proceedings D - Control Theory and Applications 129, 242–250.
  * Fedus et al. (2020) Fedus, W., Ramachandran, P., Agarwal, R., Bengio, Y., Larochelle, H., Rowland, M., Dabney, W., 2020.  Revisiting fundamentals of experience replay, in: Proceedings of the 37th International Conference on Machine Learning, PMLR. pp. 3061–3071.
  * García et al. (1989) García, C.E., Prett, D.M., Morari, M., 1989.  Model predictive control: Theory and practice—A survey.  Automatica 25, 335–348.
  * Gerber and Li (1981) Gerber, H.U., Li, S.Y.R., 1981\.  The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain.  Stochastic Proc. their App. 11, 101–108.
  * Glaz et al. (2006) Glaz, J., Kulldorff, M., Pozdnyakov, V., Steele, J.M., 2006\.  Gambling teams and waiting times for patterns in two-state Markov chains.  J. Appli. Probability 43, 127–140.
  * Guerriero et al. (2009) Guerriero, M., Willett, P., Glaz, J., 2009.  Distributed target detection in sensor networks using scan statistics.  IEEE Transactions on Signal Processing 57, 2629–2639.
  * Han (2020) Han, S., 2020.  Localized learning of robust controllers for networked systems with dynamic topology, in: Pro. 2nd Conf. Learning Dynamics Control, PMLR. pp. 687–696.
  * Han and Chung (2022) Han, S., Chung, S.J., 2022\.  Incremental nonlinear stability analysis for stochastic systems perturbed by Lévy noise.  International Journal of Robust and Nonlinear Control 32, 7174–7201.
  * Han et al. (2022) Han, S., Chung, S.J., Gustafson, J., 2022.  Congestion Control of Vehicle Traffic Networks by Learning Structural and Temporal Patterns, in: Proceedings of the 5th Conference on Learning for Dynamics and Control (L4DC).  Under review.[Link].
  * Hanmer (2013) Hanmer, R.S., 2013.  Patterns for fault tolerant software.  John Wiley & Sons, USA.
  * Ho et al. (2021) Ho, D., Le, H., Doyle, J., Yue, Y., 2021.  Online robust control of nonlinear systems with large uncertainty, in: Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR. pp. 3475–3483.
  * Jéron et al. (2008) Jéron, T., Marchand, H., Genc, S., Lafortune, S., 2008\.  Predictability of sequence patterns in discrete event systems.  IFAC Proceedings Volumes 41, 537–543.
  * Jéron et al. (2006) Jéron, T., Marchand, H., Pinchinat, S., Cordier, M.O., 2006\.  Supervision patterns in discrete event systems diagnosis, in: 8th Int. Workshop Discrete Event Sys., pp. 262–268.
  * Kipf and Welling (2017) Kipf, T.N., Welling, M., 2017\.  Semi-Supervised Classification with Graph Convolutional Networks, in: Proceedings of the 5th International Conference on Learning Representations.
  * van Leeuwaarden (2006) van Leeuwaarden, J.S.H., 2006.  Delay analysis for the fixed-cycle traffic-light queue.  Transportation Science 40, 189–199.
  * Lengyel and Dayan (2007) Lengyel, M., Dayan, P., 2007\.  Hippocampal contributions to control: The third way, in: Platt, J., Koller, D., Singer, Y., Roweis, S. (Eds.), Advances in Neural Information Processing Systems, Curran Associates, Inc.. pp. 1–8.
  * Li (1980) Li, S.Y.R., 1980.  A Martingale Approach to the Study of Occurrence of Sequence Patterns in Repeated Experiments.  Annals Probability 8, 1171 – 1176.
  * Li et al. (2018) Li, Y., Yu, R., Shahabi, C., Liu, Y., 2018.  Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting, in: International Conference on Learning Representations.
  * Lu et al. (2013) Lu, J., Li, D., Xi, Y., 2013\.  Constrained model predictive control synthesis for uncertain discrete-time Markovian jump linear systems.  IET Control Theory & Applications 7, 707–719.
  * Mesquita and Hespanha (2012) Mesquita, A.R., Hespanha, J.P., 2012\.  Jump control of probability densities with applications to autonomous vehicle motion.  IEEE Transactions on Automatic Control 57, 2588–2598.
  * Nagabandi et al. (2018) Nagabandi, A., Kahn, G., Fearing, R.S., Levine, S., 2018\.  Neural Network Dynamics for Model-Based Deep Reinforcement Learning with Model-Free Fine-Tuning, in: 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 7559–7566.  doi:10.1109/ICRA.2018.8463189.
  * Nakka et al. (2021) Nakka, Y.K., Liu, A., Shi, G., Anandkumar, A., Yue, Y., Chung, S.J., 2021\.  Chance-constrained trajectory optimization for safe exploration and learning of nonlinear systems.  IEEE Robotics and Automation Letters , 389–396.
  * O’Connell et al. (2022) O’Connell, M., Shi, G., Shi, X., Azizzadenesheli, K., Anandkumar, A., Yue, Y., Chung, S.J., 2022.  Neural-fly enables rapid learning for agile flight in strong winds.  Science Robotics 7, 1–15.
  * Park and Kwon (2002) Park, B.G., Kwon, W.H., 2002\.  Robust one-step receding horizon control of discrete-time Markovian jump uncertain systems.  Automatica 38, 1229–1235.
  * Pozdnyakov (2008) Pozdnyakov, V., 2008.  On occurrence of patterns in Markov chains: Method of gambling teams.  Statistics Probability Lett. 78, 2762–2767.
  * Pozdnyakov and Kulldorff (2006) Pozdnyakov, V., Kulldorff, M., 2006\.  Waiting times for patterns and a method of gambling teams.  American Math. Monthly 113, 134–143.
  * Pozdnyakov and Steele (2014) Pozdnyakov, V., Steele, J.M., 2014\.  Scan Statistics: Pattern Relations and Martingale Methods.  https://faculty.wharton.upenn.edu/wp-content/uploads/2014/06/Pozdnyakov_Steele-Patterns_survey.pdf.
  * Pritzel et al. (2017) Pritzel, A., Uria, B., Srinivasan, S., Badia, A.P., Vinyals, O., Hassabis, D., Wierstra, D., Blundell, C., 2017\.  Neural Episodic Control, in: Precup, D., Teh, Y.W. (Eds.), Proceedings of the 34th International Conference on Machine Learning, PMLR. pp. 2827–2836.
  * Reif et al. (1999) Reif, K., Gunther, S., Yaz, E., Unbehauen, R., 1999\.  Stochastic stability of the discrete-time extended Kalman filter.  IEEE Transactions on Automatic Control 44, 714–728.
  * Richards and How (2006) Richards, A., How, J., 2006\.  Robust variable horizon model predictive control for vehicle maneuvering.  International Journal of Robust and Nonlinear Control 16, 333 – 351.
  * Rusek et al. (2020) Rusek, K., Suárez-Varela, J., Almasan, P., Barlet-Ros, P., Cabellos-Aparicio, A., 2020.  Routenet: Leveraging graph neural networks for network modeling and optimization in sdn.  IEEE Journal on Selected Areas in Communications 38, 2260–2270.
  * Saboori and Khorasani (2015) Saboori, I., Khorasani, K., 2015\.  Actuator fault accommodation strategy for a team of multi-agent systems subject to switching topology.  Automatica 62, 200–207.
  * Schuurmans and Patrinos (2021) Schuurmans, M., Patrinos, P., 2021\.  Data-driven distributionally robust control of partially observable jump linear systems, in: 2021 60th IEEE Conference on Decision and Control (CDC), pp. 4332–4337.
  * Shi and Li (2015) Shi, P., Li, F., 2015.  A survey on Markovian jump systems: Modeling and design.  International Journal of Control, Automation and Systems 13, 1–16.
  * Shim et al. (2012) Shim, T., Adireddy, G., Yuan, H., 2012.  Autonomous vehicle collision avoidance system using path planning and model-predictive-control-based active front steering and wheel torque control.  Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering 226, 767–778.
  * Theodorou et al. (2010) Theodorou, E., Buchli, J., Schaal, S., 2010.  A generalized path integral control approach to reinforcement learning.  Journal of Machine Learning Research 11, 3137–3181.
  * Verma et al. (2018) Verma, A., Murali, V., Singh, R., Kohli, P., Chaudhuri, S., 2018.  Programmatically interpretable reinforcement learning, in: Dy, J., Krause, A. (Eds.), Proceedings of the 35th International Conference on Machine Learning, PMLR. pp. 5045–5054.
  * Vidal et al. (2002) Vidal, R., Chiuso, A., Soatto, S., 2002.  Observability and identifiability of jump linear systems, in: Proceedings of the 41st IEEE Conference on Decision and Control, 2002., pp. 3614–3619.
  * Wang et al. (2018) Wang, Y.S., Matni, N., Doyle, J., 2018.  Separable and localized system level synthesis for large-scale systems.  IEEE Transactions on Automatic Control 63, 4234–4249.
  * Willems and Polderman (1997) Willems, J.C., Polderman, J.W., 1997\.  Introduction to Mathematical Systems Theory : A Behavorial Approach.  Texts in Applied Mathematics, Springer, New York.
  * Xiong et al. (2005) Xiong, J., Lam, J., Gao, H., Ho, D.W., 2005.  On robust stabilization of Markovian jump systems with uncertain switching probabilities.  Automatica 41, 897–903.
  * Xue and Matni (2021) Xue, A., Matni, N., 2021.  Data-driven system level synthesis, in: Jadbabaie, A., Lygeros, J., Pappas, G.J., Parrilo, P., Recht, B., Tomlin, C.J., Zeilinger, M.N. (Eds.), Proceedings of the 3rd Conference on Learning for Dynamics and Control, PMLR. pp. 189–200.
  * Yu et al. (2020) Yu, C., Shi, G., Chung, S.J., Yue, Y., Wierman, A., 2020\.  The power of predictions in online control, in: Proceedings of the 34th International Conference on Neural Information Processing Systems, Curran Associates Inc., Red Hook, NY, USA. pp. 1–11.
  * Zheng et al. (2021) Zheng, K., Shi, D., Shi, L., 2021.  Learning hidden markov models for linear gaussian systems with applications to event-based state estimation.  Automatica 128, 109560\.
  * Zhou et al. (1996) Zhou, K., Doyle, J.C., Glover, K., 1996.  Robust and Optimal Control.  Prentice-Hall, Inc., Upper Saddle River, NJ, USA.