Markov Decision Processes and Stochastic Control Problems on Networks

In this chapter, we study a class of problems for Markov decision process models with finite state and action spaces. We consider finite and infinite horizon models. For a finite horizon model, the problem with an expected total reward optimization criterion is considered, which can be efficiently solved by using the backward dynamic programming technique. For infinite horizon models, two basic problems are studied: the problem with an expected total discounted reward optimization criterion and the problem with an expected average reward optimization criterion. We present some classical results concerned with determining the optimal solutions to these problems and show how these results can be extended for a class of control problems on networks. The main attention is addressed to the linear programming approach for Markov decision processes and control problems on networks. Our emphasis is on formulating and studying the infinite horizon decision problems in terms of stationary strategies. We show that infinite horizon Markov decision problems with average and discounted optimization criteria can be formulated in terms of stationary strategies as classical mathematical programming problems with quasi-monotonic (quasi-convex and quasi-concave) object functions and linear constraints. In the following, we show that such quasi-monotonic programming models for infinite horizon decision problems are useful for studying stochastic games with average and discounted payoffs.