A weakly monotonic backward induction algorithm on finite bounded subsets of vector lattices

摘要

We present a new efficient and robust backward induction algorithm, which is weakly monotonic, working on bounded subsets without holes of lattices. We prove all its properties, give examples of applications, and illustrate its behavior, comparing it with the natural extension of the unidimensional algorithm presented in Puterman (Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, New York, 1994), in the sense of Topkis (Frontiers of Economic Research Series, Princeton University Press, Princeton, NJ, 1998) and White (Recent Developments in Markov Decision Processes, Academic Press, New York, 1980, 261) and showing, also experimentally, that it is much more efficient.