Optimization in Markov decision problems with transition-dependent cost functions

The traditional MDP deals with the cost function which only depends on the state, and the corresponding action. In the real world, however, there are many applications where the cost incurred depends on the particular transition as well, which makes the traditional MDP solution infeasible for these problems. In this paper, we apply the performance potential theory as an optimization tool for MDP. In particular, the notion of the expanded Markov chain is introduced to map this problem to a general form. Both computation-based and sample-path-based algorithms are developed for potential derivation. We address ourselves to the complexity-reduction techniques. Finally, we apply these techniques to the `Join the Shortest Queue' application, which is a significant component in the analysis of communication system.