## Probably Approximately Optimal Satisficing Strategies

- Russ Greiner, Dept of Computing Science; PI of AICML
- Pekka Orponen

Other Attachments: | pao-AIJ.pdf |

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), 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}, journal = {Artificial Intelligence (AIJ)}, year = 1996, }

Last Updated: April 24, 2007

Submitted by Russ Greiner