---
title: "Learning Restart Strategies"
authors:
  - "Matteo Gagliolo"
  - "Jürgen Schmidhuber"
doi: ""
url: "https://ijcai.org/proceedings/2007/127"
pdf: "https://ijcai.org/proceedings/2007/0127.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "792-796"
track: ""
keywords:
---

# Learning Restart Strategies

Matteo Gagliolo, Jürgen Schmidhuber

*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.