Enforcing ?-Regular Properties in Markov Chains by Restarting

Restarts are used in many computer systems to improve performance. Examples include reloading a webpage, reissuing a request, or restarting a randomized search. The design of restart strategies has been extensively studied by the performance evaluation community. In this paper, we address the problem of designing universal restart strategies, valid for arbitrary finite-state Markov chains, that enforce a given ?-regular property while not knowing the chain. A strategy enforces a property ? if, with probability 1, the number of restarts is finite, and the run of the Markov chain after the last restart satisfies ?. We design a simple "cautious" strategy that solves the problem, and a more sophisticated "bold" strategy with an almost optimal number of restarts