Learning Restart Strategies

Gagliolo, Matteo; Schmidhuber, Jürgen

Learning Restart Strategies

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 792-796.

Abstract

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.

Matteo Gagliolo, and Jürgen Schmidhuber. 2007. Learning Restart Strategies. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07. IJCAI, 792–796. https://ijcai.org/proceedings/2007/127

@inproceedings{ijcai2007p127,
  title     = {Learning Restart Strategies},
  author    = {Gagliolo, Matteo and Schmidhuber, Jürgen},
  booktitle = {Proceedings of the Twentieth International Joint Conference on
               Artificial Intelligence, {IJCAI-07}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ramon López de Mántaras},
  pages     = {792--796},
  year      = {2007},
  url       = {https://ijcai.org/proceedings/2007/127},
}

TY  - CPAPER
TI  - Learning Restart Strategies
AU  - Gagliolo, Matteo
AU  - Schmidhuber, Jürgen
T2  - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2007
SP  - 792
EP  - 796
UR  - https://ijcai.org/proceedings/2007/127
ER  -