|
|
Title: Discounted Deterministic Markov Decision Processes |
Name: Uri Zwick Tel Aviv University, Israel |
|
| Time:October 15th (Wednesday) 11:15-12:00 | |
| Location: Lecture Hall, FIT Building, Tsinghua University | |
| Host Unit: ITCS, Tsinghua University |
|
|
Title: Discounted Deterministic Markov Decision Processes |
Name: Uri Zwick Tel Aviv University, Israel |
|
| Time:October 15th (Wednesday) 11:15-12:00 | |
| Location: Lecture Hall, FIT Building, Tsinghua University | |
| Host Unit: ITCS, Tsinghua University |
We present an O(mn)-time algorithm for finding optimal strategies for discounted, infinite-horizon, Deterministic Markov Decision Processes (DMDP), where n is the number of vertices (or states) and m is the number of edges (or actions). This improves a recent O(mn^2)-time algorithm of Andersson and Vorobyov.
Joint work with Omid Madani and Mikkel Thorup.
Uri Zwick received his B.Sc. degree in Computer Science from the Technion, Israel Institute of Technology, and his M.Sc. and Ph.D. degrees in Computer Science from Tel Aviv University. He is currently a Professor of Computer Science in Tel Aviv University. His main research interests are: algorithms and complexity, combinatorial optimization, mathematical games, and recreational mathematITCS.
