On the block upper-triangularity of undiscounted multi-chain markov decision problems |
| |
Authors: | Norihiro Mizuno |
| |
Institution: | Graduate School of Business Administration, New York University, 90 Trinity Place, New York, NY 10006, U.S.A. |
| |
Abstract: | We show that the LP formulation for an undiscounted multi-chain Markov decision problem can be put in a block upper-triangular form by a polynomial time procedure. Each minimal block (after an appropriate dynamic revision) gives rise to a single-chain Markov decision problem which can be treated independently. An optimal solution to each single-chain problem can be connected by auxiliary dual programs to obtain an optimal solution to a multi-chain problem. |
| |
Keywords: | Markov dynamic programming finite state linear programming algorithm |
本文献已被 ScienceDirect 等数据库收录! |