Learning restart strategies

Matteo Gagliolo, Jürgen Schmidhuber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations


Restart strategies are commonly used for minimizing the computational cost of randomized algorithms, but require prior knowledge of the run-time distribution in order to be effective. We propose a portfolio of two strategies, one fixed, with a provable bound on performance, the other based on a model of run-time distribution, updated as the two strategies are run on a sequence of problems. Computational resources are allocated probabilistically to the two strategies, based on their performances, using a well-known K-armed bandit problem solver. We present bounds on the performance of the resulting technique, and experiments with a satisfiability problem solver, showing rapid convergence to a near-optimal execution time.
Original languageEnglish (US)
Title of host publicationIJCAI International Joint Conference on Artificial Intelligence
Number of pages6
StatePublished - Dec 1 2007
Externally publishedYes


Dive into the research topics of 'Learning restart strategies'. Together they form a unique fingerprint.

Cite this