Customizing exponential semi-Markov decision processes under the discounted cost criterion

Abstract

The uniformization technique is a widely used method for establishing the existence of optimal policies with certain monotonicity properties. This technique converts a semi-Markov decision process with exponential sojourn times (ESMDP) into an equivalent discrete-time Markov decision process by defining some fictitious jumps. This study proposes a new device, called customization, which can convert a given ESMDP into another equivalent ESMDP whose formulation possibly simplifies mathematical analysis. The customization technique uses the fictitious jump idea to establish the equivalence under deterministic stationary policies just like the uniformization technique. However, it allows the transition rates of the new ESMDP to be different. Moreover, it can be applied even when the transition rates of the initial ESMDP are unbounded. This flexibility can be very useful in analyzing the problems where the uniformization is not applicable or not so helpful. We analyze a complex optimal replacement problem and an infinite server queueing problem with unbounded transition rates to demonstrate the applicability and advantages of customization.