Uniform Turnpike Theorems for Finite Markov Decision Processes

A turnpike integer is the smallest finite horizon for which an optimal infinite horizon decision is the optimal initial decision. An important practical question considered in the literature is how to bound the turnpike integer using only the problem inputs. In this paper, we consider turnpike integers as a function of the discount factor. While a turnpike integer is finite for any fixed discount factor, we show that it approaches infinity in the neighborhood of a specific set of discount rates (for all but some exceptional finite Markov decision processes). We completely characterize this taboo set of discount factors and find necessary and sufficient conditions for a set of turnpike integers to be unbounded. This finding provides a cautionary tale for practitioners using point estimates of the discount factor to manage the length of rolling horizons by pointing to potential singularities in the procedure.