ISSN:
1436-6304
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung In dieser Arbeit betrachten wir mehrere Varianten der Methode der sukzessiven Approximation bei (semi-) Markoffschen Enscheidungsprozessen mit unbeschränkten Erträgen. Wessels und van Nunen haben gezeigt, daß man eine Klasse von Verfahren mit Hilfe von randomisierten Stoppzeiten erzeugen kann, wobei die Wahrscheinlichkeit, den Prozeß zur Zeitn zu stoppen, unabhängig von den Aktionen bis zur Zeitn ist. In der vorliegenden Arbeit dürfen die Stoppzeiten von den Aktionen und den Zuständen abhängen. Dadurch ist es möglich, die Klasse der Lösungsverfahren so zu erweitern, daß Eigenschaften der Erträge und der Übergangsstruktur, die von den Aktionen abhängen, bei der Entwicklung von Verfahren der sukzessiven Approximation berücksichtigt werden können. Für eine spezielle aktions-abhängige Stoppzeit besitzt der zugehörige Algorithmus die sogenannte “equal-row-sum” Eigenschaft, die beispielsweise Anwendung findet bei der Transformation eines semi-markoffschen Entscheidungsprozesses in einen gewöhnlichen Markoffschen Entscheidungsprozeß. Darüberhinaus gestattet die equal-row-sum Eigenschaft die Konstruktion guter unterer und oberer Schranken der Wertfunktion, sowie die Elimination nicht optimaler Aktionen.
Notes:
Summary In this paper we consider several variants of the standard successive-approximation method for (semi) Markov decision processes with unbounded rewards. Wessels and van Nunen have shown that a class of variants can be generated by randomized stopping times, where the probability of “stopping” the process at timen is independent of the actions taken up to timen. In this paper we allow the stopping time to depend on the actions as well as the states. This makes it possible to extend the class of solution techniques in such a way that properties of the reward and transition structure depending on the actions can be exploited in the development of appropriate successive-approximation methods. For a special actions-dependent stopping time the corresponding algorithm possesses the so-called “equal-row-sum” property, which can be used, for example, to transform semi-Markov decision processes into ordinary Markov decision processes. Moreover, the equal-row-sum transformation allows for good extrapolation to upper and lower bounds and elimination of non-optimal actions.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01783952
Permalink