Selecting approximately-optimal actions in complex structured domains
Leslie Pack Kaelbling, Luis E. Ortiz · 2002
We study the problem of action selection in structured domains. In general, the provided structural decomposition of the problem is not sufficient to allow tractable computation of the exact solution. Hence, we concentrate on obtaining near-optimal solutions with some guaranteed qualities. In this work, the main intuition we exploit is that the problem of action selection is primarily a comparison rather than an estimation task. From this point of view, we consider sampling methods for action selection. We propose methods to reduce the number of samples required to obtain near-optimal actions. We present results on the number of samples needed to obtain highly probable, near-optimal actions. In addition, we present a comparison-based sampling method and a heuristic stopping rule that can potentially reduce the total number of samples. Although estimation is not a primary task, better estimators lead to better action selection. We present update rules to adaptively improve the sampling distribution and hence the resulting estimators. We present preliminary validation results on both made-up and real models. The results show the potential of the methods for action selection and improving estimation. Throughout the document, we present remaining open questions and suggest future work.