Negatively isotone optimal policies for random walk type Markov decision processes

Summary

This paper considers a random walk type Markov decision process in which the state spaceI is an integer subset of IR^m, and the action spaceK is independent ofi εI. The natural order

, overI, and a quasi order,

′, overK, is assumed, together with aconditional convexity assumption on the returns {r ^k_i }, and certain other assumptions about these rewards and the transition probabilities in relationship to the orders

and

′.A negatively isotone policy is one for whichi

i′→δ(i)⊁′)δ(i′) (i.e.δ(i)

′δ(i)′ orδ(i′)

′δi)). It is shown that, under specified conditions, a negatively isotone optimal policy exists. Some consideration is given to computational implications in particular relationship to Howard's policy space method.

Zusammenfassung

Wir betrachten einen Markovschen Entscheidungsprozeß vom random walk Typ. Der ZustandsraumI sei eine Teilmenge des IR^m, wobeii εI ganzzahlige Komponenten habe. Die MengeK der zulässigen Aktionen ini εI sei unabhängig voni εI. Sei

die natürliche Ordnung aufI und

′ sei eine Quasiordnung aufK. Die Erträge {r ^k_i }seienbedingt konvex, darüberhinaus seien weitere Voraussetzungen über diese Erträge und die Übergangswahrscheinlichkeiten in Bezug auf die Ordnungen

und

′ erfüllt. Eine Politik δ heißt negativ isoton, falls ausi

i′ folgtδi⊁′δ(i′) (d. h.δ(i)

′δ(i)′ oderδ(i)′

′δ(i)′). Wir zeigen, daß unter gewissen Voraussetzungen einenegativ isotone optimale Politik existiert: Auch diskutieren wir einige Folgerungen für die Numerik, insbesondere hinsichtlich Howards Politikiteration.