Stochastic infinite horizon optimization with average cost criterion.

Abstract

We consider the stochastic infinite horizon optimization problem which seeks to minimize average cost. Observe that any solution which makes poor decisions for any finite amount of time and then selects wisely can be average optimal. It is our intent to eliminate these types of average optimal solutions from consideration since they are difficult to justify over finite horizons. Instead, we seek a method for finding average optimal solutions with both effective short-run and long-run behavior. An efficient solution has been defined in a deterministic framework to be one which is optimal to every state it passes through. Thus, its behavior over the short-term is optimal in the sense that it reaches all its states with minimal cost. It has been shown that for deterministic problems which satisfy a bounded reachability condition, efficient solutions are average optimal. We transform the stochastic problem into a deterministic one to utilize many of these deterministic results. However, the transformed stochastic problem does not satisfy the bounded reachability property, so this research introduces the notion of near reachability. Furthermore, we extend the idea of an efficient solution to an $\epsilon$-efficient solution. We also develop a property which includes a near reachability condition and a regulated cost differences requirement. The $\epsilon$-efficient solutions are shown to be average optimal for problems which satisfy this property which we refer to as Property BNR. We prove that nonhomogeneous Markov Decision Processes satisfy Property BNR, hence, an interesting class of problems can be solved for the minimal average cost objective. Furthermore, an algorithm designed to solve the infinite horizon undiscounted deterministic problem is modified for the stochastic problem. This algorithm finds the first best decision to the infinite horizon problem in a finite amount of time. The procedure may be repeated iteratively to build an optimal sequence of decisions. The dissertation concludes with an application to a machine down-time minimization problem.