Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks |
| |
Authors: | Guy Even Alexander Zadorojniy |
| |
Institution: | 1. School of Electrical Engineering, Tel-Aviv Univ., Tel-Aviv, 69978, Israel 2. IBM Research, Mount Carmel, Haifa, 31905, Israel
|
| |
Abstract: | We consider the subclass of linear programs that formulate Markov Decision Processes (mdps). We show that the Simplex algorithm with the Gass-Saaty shadow-vertex pivoting rule is strongly polynomial for a subclass of mdps, called controlled random walks (CRWs); the running time is O(|S|3?|U|2), where |S| denotes the number of states and |U| denotes the number of actions per state. This result improves the running time of Zadorojniy et al. (Mathematics of Operations Research 34(4):992?C1007, 2009) algorithm by a factor of |S|. In particular, the number of iterations needed by the Simplex algorithm for CRWs is linear in the number of states and does not depend on the discount factor. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|