Countable-State, Continuous-Time Dynamic Programming with Structure

We consider the problem P of maximizing the expected discounted reward earned in a continuous-time Markov decision process with countable state and finite action space. (The reward rate is merely bounded by a polynomial.) By examining a sequence 〈p_N〉 of approximating problems, each of which is a semi-Markov decision process with exponential transition rate Λ_N, Λ_N ↗ ∞, we are able to show that P is obtained as the limit of the P_N. The value in representing P as the limit of P_N is that structural properties present in each P_N persist, in both the finite and the infinite horizon problem. Three queuing optimization models illustrating the method are given.