Nearly Optimal Controls of Markovian Systems

This chapter is concerned with asymptotically optimal controls of Markovian systems with weak and strong interactions in discrete time. The primary motivation of our study stems from many applications in operations research such as resource allocation, queueing networks, machine replacement, and command control. Due to the complexity of the real-world problems, one often has to deal with large dimensional systems under uncertainty. Frequently, the underlying Markov chain displays jump behavior having different rates of jumps (some of them vary fast, whereas others change slowly). It is natural to divide the states of such Markov chain into several groups so that transitions among the states within each group occur much more frequently than the transitions among the states belonging to different groups. The basic idea of our approach is to aggregate the states in each group as a single state and to derive a limit problem of smaller dimension. Using an optimal control of the limit problem, we construct controls of the original problem, leading to asymptotic optimality. Our hierarchical approach provides an efficient tool for treating large and complex systems and for finding approximately optimal solutions.