A stopping rule for forecast horizons in nonhomogeneous Markov decision processes

The authors formulate a mixed integer program to determine whether a finite time horizon is a forecast horizon in a nonhomogeneous Markov decision process. They give a Bender’s decomposition approach to solving this problem that evaluates the stopping rule, eliminates some suboptimal combinations of actions, and yeilds bounds on the maximum error that could result from the selection of a candidate action in the initial stage. The integer program arising from the decomposition has special properties that allow efficient solution. The authors illustrate the approach with numerical examples.