Reward revision and the average reward markov decision process

Summary We integrate two numerical procedures for solving the average reward Markov decision process (MDP), standard successive approximations and modified policy iteration with reward revision. Reward revision is the process of revising the reward structure of a second, more computationally desirable MDP so as to produce, in the limit, an optimality equation having a fixed point identical to that associated with the original MDP. A numerical study indicates that for MDP's having a non-sparse transition structure with a small number of relatively large entries per row, the addition of reward revision can have significant computational benefits.

---

Zusammenfassung Zur Lösung Markovscher Entscheidungsprozesse (MDP) mit Durchschnitts-Kriterium werden zwei numerische Verfahren, nämlich sukzessive Approximation und modifizierte Politik-Iteration, mit einer Transformation, der sogenannten 'Reward-Revision, kombiniert. Bei dieser Transformation werden die Übergangswahrscheinlichkeiten so abgeändert (ausgedünnt), daß das neue Modell sich numerisch günstiger verhält. Dazu müssen die einstufigen Erträge so revidiert werden, daß die Optimalitäts-Gleichung des neuen Modells im Limes mit der des ursprünglichen übereinstimmt. Numerische Untersuchungen zeigen, daß für MDP mit stark besetzten Übergangsmatrizen, bei denen nur an wenigen Stellen je Zeile große Werte stehen, die Anwendung von 'Reward Revision zu wesentlichen Einsparungen an Rechenaufwand führen kann.

---

---

Research supported by NSF Grant ECS-8319355