|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-95-016
Probably
Approximately Optimal Satisficing Strategies
Russell
Greiner
Siemens Corporate Research
Pekka
Orponen
Department of Computer Science
University of Helsinki
Abstract
A satisficing search problem consists of a set of
probabilistic experiments to be performed in some order, seeking a
satisfying configuration of successes and failures. The expected cost
of the search depends both on the success probabilities of the individual
experiments, and on the search strategy, which specifies
the order in which the experiments are to be performed. A strategy
that minimizes the expected cost is optimal. Earlier work
has provided ``optimizing functions'' that compute optimal strategies
for certain classes of search problems from the success probabilities
of the individual experiments. We extend those results by providing
a general model of such strategies, and an algorithm \pao\ that identifies
an approximately optimal strategy when the probability values are
not known. The algorithm first estimates the relevant probabilities
from a number of trials of each undetermined experiment, and then
uses these estimates, and the proper optimizing function, to identify
a strategy whose cost is, with high probability, close to optimal.
We also show that if the search problem can be formulated as an and-or
tree, then the PAO algorithm can also ``learn while doing'', i.e.
gather the necessary statistics while performing the search.
Download Compressed
Postscript
|