Discounted Deterministic Markov Decision Processes and Discounted All-Pairs Shortest Paths

Abstract

We present algorithms for finding optimal strategies for discounted, infinite-horizon, Determinsitc Markov Decision Processes (DMDPs). Our fastest algorithm has a worst-case running time of O(mn), improving the recent bound of O(mn²) obtained by Andersson and Vorbyov [2006]. We also present a randomized O(m^1/2n²)-time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving an O(mn²)-time algorithm that can be obtained using ideas of Papadimitriou and Tsitsiklis [1987].