This paper examines restart strategies for algorithms whose successful termination depends on an unknown parameter $λ$. After each restart, $λ$ is increased, until the algorithm terminates successfully. It is assumed that there is a unique, unknown, optimal value for $λ$. For the algorithm to run successfully, this value must be reached or surpassed. The key question is whether there exists an optimal strategy for selecting $λ$ after each restart taking into account that the computational costs (runtime) increases with $λ$. In this work, potential restart strategies are classified into parameter-dependent strategy types. A loss function is introduced to quantify the wasted computational cost relative to the optimal strategy. A crucial requirement for any efficient restart strategy is that its loss, relative to the optimal $λ$, remains bounded. To this end, upper and lower bounds of the loss are derived. Using these bounds it will be shown that not all strategy types are bounded. However, for a particular strategy type, where $λ$ is increased multiplicatively by a constant factor $λ$, the relative loss function is bounded. Furthermore, it will be demonstrated that within this strategy type, there exists an optimal value for $λ$ that minimizes the maximum relative loss. In the asymptotic limit, this optimal choice of $λ$ does not depend on the unknown optimal $λ$.