On the Complexity of Discounted Markov Decision process
主 题: On the Complexity of Discounted Markov Decision process
报告人: Mengdi Wang, Princeton University
时 间: 2017-06-12 14:00 - 2017-06-12 15:00
地 点: Room 29, Quan Zhai, BICMR
We provide the first sublinear running time upper bound and a nearly matching lower bound for the discounted Markov decision problem.
\n
\nUpper bound: We propose a randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. By leveraging the value-policy duality, the algorithm adaptively samples state transitions and makes exponentiated primal-dual updates. We show that it finds an ε-optimal policy using nearly-linear running time in the worst case. For Markov decision processes that are ergodic under every stationary policy, we show that the algorithm finds an ε-optimal policy using running time linear in the total number of state-action pairs, which is sublinear in the input size. These results provide new complexity benchmarks for solving stochastic dynamic programs.
\n
\nLower bound: We also show that there exists computational lower bound on the run time of any algorithm for solving the MDP.
\n
\n\t
\n<\/div>
