Probably Approximately Optimal Satisficing Strategies
Full Text:
pao.ps 
A
satisficing search problem consists of a set of probabilistic experiments tobe performed in some order, seeking a satisfying configuration of successesand failures. The expected cost of the search depends both on the successprobabilities 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 byproviding a general model of such strategies, and an algorithm PAO thatidentifies 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 thes earch 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.
Citation
R. Greiner,
P. Orponen.
"Probably Approximately Optimal Satisficing Strategies".
Artificial Intelligence (AIJ), 82(1-2), pp 21-44, April 1996.
| Keywords: |
optimal, strategies, PAC, PALO, machine learning |
| Category: |
In Journal |
BibTeX
@article{Greiner+Orponen:AIJ96,
author = {Russ Greiner and Pekka Orponen},
title = {Probably Approximately Optimal Satisficing Strategies},
Volume = "82",
Number = "1-2",
Pages = {21-44},
journal = {Artificial Intelligence (AIJ)},
year = 1996,
}Last Updated: November 15, 2019
Submitted by Sabina P 
