Hamiltonian cycles and singularly perturbed Markov chains

• 成果类型: Article
• 署名作者: Ejov, V; Filar, JA; Nguyen, MT
• 署名单位: University of South Australia; Defence Science & Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1030.0066
• 发表日期: 2004
• 页码: 114-131
• 关键词: DECISION-PROCESSES

摘要

We consider the Hamiltonian cycle problem embedded in a singularly perturbed Markov decision process. We also consider a functional on the space of deterministic policies of the process that consists of the (1,1)-entry of the fundamental matrices of the Markov chains induced by the same policies. We show that when the perturbation parameter, epsilon, is less than or equal to 1/N-2, the Hamiltonian cycles of the directed graph are precisely the minimizers of our functional over the space of deterministic policies. In the process, we derive analytical expressions for the possible N distinct values of the functional over the, typically, much larger space of deterministic policies.