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

Bidragets oversatte titel: Discounted deterministic Markov decision processes and discounted all-pairs shortest paths

Omid Madani, Mikkel Thorup, Uri Zwick

11 Citationer (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].

Bidragets oversatte titel	Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
Originalsprog	Engelsk
Tidsskrift	ACM Transactions on Algorithms
Vol/bind	6
Udgave nummer	2
ISSN	1549-6325
Status	Udgivet - 1 mar. 2010
Udgivet eksternt	Ja

Citationsformater

@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

Fingeraftryk

Citationsformater