Temporal Robustness in Discrete Time Linear Dynamical Systems
This work addresses uncertainty in time horizons for applications like cybersecurity and health risk management, offering incremental improvements in robust cost estimation methods.
The paper tackles the problem of uncertainty in time horizons for discrete time linear dynamical systems, such as Markov chains, by analyzing cost estimation as a distributionally robust optimization task using Wasserstein ambiguity sets, and provides polynomial-time algorithms and hardness results validated on real-world cybersecurity and health data.
Discrete time linear dynamical systems, including Markov chains, have found many applications including in security settings such as in cybersecurity operations center (CSOC) management and in managing health risks. However, in these two scenarios, there is uncertainty about the time horizon for which the system runs. This creates uncertainty about the cost (or reward) incurred based on the state distribution when the system stops. Given past data samples of how long a system ran, we theoretically analyze the cost incurred at the stop of the system as a distributional robust cost estimation task in a Wasserstein ambiguity set. Towards this, we show an equivalence between a discrete time Markov Chain on a probability simplex and a global asymptotic stable (GAS) discrete time linear dynamical system, allowing us to base our study on a GAS system only. Then, we provide various polynomial time algorithms and hardness results for different cases in our theoretical study, including a novel proof of a fundamental result about Wassertein distance based polytope. We experiment with real world data in CSOC domain and prior data in health domain to reveal the benefits of our model and approach.