Discount-isotone policies for Markov decision processes

Summary

This paper considers infinite horizon discounted Markov decision processes and conditions under which discount-isotone optimal policies exist. Given partial orders over the state and action spaces, a set of discount-isotone optimal policies is a set of optimal policies, one for each discount factor in a given set, such that, for each state, the optimal actions are partially ordered in such a manner as to match the ordering of the discount factors. It is easier to solve problems with small discount factors and the induced partial ordering facilitates the solutions for higher discount factor levels.

Zusammenfassung

Für unendlich-stufige diskontierte Markovsche Entscheidungsprozesse werden Bedingungen angegeben, unter denen sogenannte “diskont-isotone” optimale Politiken existieren. Eine diskont-isotone Familie von optimalen Politiken liegt vor, wenn die Zustands- und Aktionenräume halbgeordnet sind und für eine Menge von Diskontierungsfaktoren je eine optimale Politik existiert, so daß in jedem Zustand die optimalen Aktionen isoton vom Diskontierungsfaktor abhängen. Es kann günstiger sein, zunächst Probleme mit kleinem Diskontierungsfaktor zu lösen und dann die Isotonie-Eigenschaften zur Lösung für größere Diskontierungsfaktoren heranzuziehen.