Expected Survival-Time Bounds for Robust Optimization Over Time under Isotropic Gaussian Dynamics
arXiv:2607.27280
The paper derives theoretical lower and upper bounds on the expected survival time of a fixed solution in dynamic environments that evolve according to isotropic Gaussian dynamics, and validates the results with Monte Carlo simulations.
Abstract
Robust Optimization Over Time (ROOT) is a recent branch of evolutionary dynamic optimization that seeks solutions capable of remaining effective across multiple consecutive environments. Unlike the traditional track-the-moving-optimum (TMO) paradigm, which reoptimizes after every environmental change, ROOT explicitly values persistence. Although the field has grown considerably, most contributions remain algorithmic and empirical, leaving several fundamental properties poorly understood from a theoretical perspective. One such property is survival time, defined as the number of future environments in which a deployed solution continues to satisfy a prescribed quality threshold. While survival time is widely used as a measure of temporal robustness, little is known about how its expected value depends on environmental dynamics, deployment quality, or problem characteristics. This paper studies expected survival time for a fixed deployed solution under isotropic Gaussian environmental dynamics. Modeling survival as a discrete first-exit problem, we derive a rigorous lower bound and a computable multi-step upper bound. The analysis shows that expected survival scales as in slowly varying environments and approaches its minimum value of one future change in high dimensions. A comprehensive Monte Carlo study validates the theoretical predictions, examines sensitivity to modeling assumptions and parameter uncertainty, and illustrates how the bounds can support deployment decisions after optimization. The resulting framework provides an analytical characterization of deployment lifetime and identifies when a required deployment horizon can be guaranteed, ruled out, or remains analytically unresolved.