Linear Programming and Constrained Average Optimality for General Continuous-Time Markov Decision Processes in History-Dependent Policies
Authors:
- Xianping GuoXGXianping Guo
- Yonghui HuangYHYonghui Huang
- Xinyuan SongXSXinyuan Song
- 1 January 2012
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 50 (1) , 23-47
Abstract
This paper attempts to study the constrained average optimality for continuous-time Markov decision processes in the class of randomized history-dependent policies. The states and actions are in general Polish spaces, and the transition rates are allowed to be unbounded. The optimality criterion to be optimized is expected average costs, multiple constraints are imposed on similar expected average costs, and all costs may be unbounded from above and from below. Under suitable conditions, we first show the existence of a constrained optimal policy by improving the concept of a stable policy in the previous literature and using the analogue of the forward Kolmogorov equation. Then, we develop a linear program (LP), which is equivalent to the constrained optimality problem and is used to obtain a constrained optimal policy. By introducing suitable operators and conditions, we further establish the dual program (DP) of the LP, show that the LP and DP are solvable, and show that there is no duality gap between them. Finally, we use a cash flow model and a controlled birth and death system to illustrate the applications of our main results.Keywords
This publication has 34 references indexed in Scilit:
- Discounted continuous-time constrained Markov decision processes in Polish spacesThe Annals of Applied Probability, 2011
- Constrained Optimization for Average Cost Continuous-Time Markov Decision ProcessesIEEE Transactions on Automatic Control, 2007
- A survey of recent results on continuous-time Markov decision processesTOP, 2006
- Average optimality for continuous-time Markov decision processes in Polish spacesThe Annals of Applied Probability, 2006
- Optimal Control of Ergodic Continuous-Time Markov Chains with Average Sample-Path RewardsSIAM Journal on Control and Optimization, 2005
- Continuous Time Discounted Jump Markov Decision Processes: A Discrete-Event ApproachMathematics of Operations Research, 2004
- A note on optimality conditions for continuous-time Markov decision processes with average cost criterionIEEE Transactions on Automatic Control, 2001
- Bias Optimality in Controlled Queueing SystemsJournal of Applied Probability, 1998
- Infinite Linear Programming and Multichain Markov Control Processes in Uncountable SpacesSIAM Journal on Control and Optimization, 1998
- Exponential and Uniform Ergodicity of Markov ProcessesThe Annals of Probability, 1995