Approximations and bounds for a generalized optimal stopping problem

We study a finite-horizon nonstationary Markovian decision problem, that can be interpreted as generalized optimal stopping and whose solution via the usual dynamic programming is in most practical cases not feasible from a computational point of view. Under certain assumptions, most importantly stochastic monotonicity, upper and lower bounds are obtained for optimal values and decisions using a reduced dynamic programming. From this, a suboptimal policy is derived with an upper bound on its suboptimality. Computational aspects and a particular application from optimal exploratory oil drilling are discussed.

---

Zusammenfassung In der Arbeit wird ein nichtstationäres Markowsches Entscheidungsproblem mit endlichem Planungshorizont betrachtet, das als verallgemeinertes Stopp-Problem interpretiert werden kann. Die numerische Lösung des Problems mit Hilfe der üblichen Methode der dynamischen Optimierung ist in der Regel zu rechenaufwendig. Es wird deshalb eine Methode der approximativen Lösung des Problems (mit gewissen Einschränkungen) vorgeschlagen, und es werden obere und untere Schranken für den Optimalwert hergeleitet. Ferner wird eine suboptimale Politik mit einer oberen Schranke für die Suboptimalität angegeben. Abschließend wird ein praktisches Anwendungsbeispiel (optimale Versuchsbohrungen nach Öl) diskutiert, an dem auch rechentechnische Aspekte des entwickelten Lösungsverfahrens erläutert werden.

---

---

Research partially supported by the Consiglio Nazionale delle Ricerche (CNR), Italy, through contract n.80.02343.01 and through GNAFA.