Monotonicity in infinite horizon optimization.

Abstract

Many real world problems with time-varying characteristic and unbounded horizon can be modeled as an infinite horizon nonhomogeneous Markov decision problem. Examples include the stochastic demand production planning problem and the optimal stopping problem. One way to solve these problems is by using a forecast horizon approach which is to solve a finite horizon problem with the property that data beyond this horizon do not affect the optimality of the first period policy. This resolves the following dilemma. On one hand, we need a sufficient amount of data so that our decision is not shortsighted. On the other hand, we would like to minimize the amount of forecasting we need to do because it is usually expensive and difficult to justify. Many results have already been established in the infinite horizon non-homogeneous Markov decision problem context. However, uniqueness of an infinite horizon optimal policy is often assumed. Instead, we establish existence and discovery of forecast horizons by exploiting a monotonicity property of the first optimal policy as the problem horizon grows.