Discounted deterministic Markov decision processes and discounted all-pairs shortest paths

Omid Madani; Mikkel Thorup; Uri Zwick

Discounted deterministic Markov decision processes and discounted all-pairs shortest paths

Omid Madani, Mikkel Thorup, Uri Zwick

11 Citations (Scopus)

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].

Translated title of the contribution	Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
Original language	English
Journal	ACM Transactions on Algorithms
Volume	6
Issue number	2
ISSN	1549-6325
Publication status	Published - 1 Mar 2010
Externally published	Yes

Cite this

@article{b15ef07fe46f409cba9ef1f2abd3f376,

title = "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(mn2) obtained by Andersson and Vorbyov [2006]. We also present a randomized O(m1/2n2)-time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving an O(mn2)-time algorithm that can be obtained using ideas of Papadimitriou and Tsitsiklis [1987].",

author = "Omid Madani and Mikkel Thorup and Uri Zwick",

note = "Announced at SODA'09",

year = "2010",

month = mar,

day = "1",

language = "English",

volume = "6",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery, Inc.",

number = "2",

}

TY - JOUR

T1 - Discounted deterministic Markov decision processes and discounted all-pairs shortest paths

AU - Madani, Omid

AU - Thorup, Mikkel

AU - Zwick, Uri

N1 - Announced at SODA'09

PY - 2010/3/1

Y1 - 2010/3/1

N2 - 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(mn2) obtained by Andersson and Vorbyov [2006]. We also present a randomized O(m1/2n2)-time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving an O(mn2)-time algorithm that can be obtained using ideas of Papadimitriou and Tsitsiklis [1987].

AB - 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(mn2) obtained by Andersson and Vorbyov [2006]. We also present a randomized O(m1/2n2)-time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving an O(mn2)-time algorithm that can be obtained using ideas of Papadimitriou and Tsitsiklis [1987].

M3 - Journal article

SN - 1549-6325

VL - 6

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 2

ER -

Discounted deterministic Markov decision processes and discounted all-pairs shortest paths

Abstract

Fingerprint

Cite this