We are developing a general framework for using learned Bayesian models for
decision-theoretic control of search and reasoningalgorithms. We illustrate the
approach on the specific task of controlling both general and domain-specific
solvers on a hard class of structured constraint satisfaction problems. A
successful strategyfor reducing the high (and even infinite) variance in
running time typically exhibited by backtracking search algorithms is to cut
off and restart the search if a solution is not found within a certainamount of
time. Previous work on restart strategies have employed fixed cut off values.
We show how to create a dynamic cut off strategy by learning a Bayesian model
that predicts the ultimate length of a trial based on observing the early
behavior of the search algorithm. Furthermore, we describe the general
conditions under which a dynamic restart strategy can outperform the
theoretically optimal fixed strategy.

本文提出了一个利用贝叶斯模型为决策性控制搜索和推理算法提供通用框架的方法，并通过结构化约束满足问题的一种难类任务，演示了该方法的应用。本文进一步探讨了如何通过学习贝叶斯模型来创建动态截止策略，以及在哪些情况下动态重启策略能够超越理论上最优的固定策略。