Degeneracy in discrete infinite horizon optimization.
Sarah M. Ryan · Deep Blue (University of Michigan) · 1988
Infinite horizon sequential decision problems may be solved by identifying a solution horizon, a finite time horizon that is long enough to yield an optimal initial decision for the infinite horizon problem. Nearly all solution horizon existence results in the literature require non-degeneracy, i.e., that the optimal initial decision for the infinite horizon problem be unique. This dissertation studies a general infinite horizon problem with discrete decisions and discounted costs. We examine the appropriateness of assuming nondegeneracy and then present methods for solving problems that may be degenerate. Uniqueness of the optimal initial decision depends on the interest rate used to discount costs. We characterize the interest rates that may allow degeneracy, and then present a general example of a problem with discrete decisions in which every reasonable interest rate may lead to degeneracy. We conclude that degeneracy is a serious theoretical problem. One approach for resolving degeneracy is based on perturbing the cost of each initial decision in order to guarantee that the optimal initial decision will be unique. A general cost-based algorithm can then be used to discover the optimal initial decision. We also calculate horizons that yield an initial decision for a strategy with cost arbitrarily close to optimal. The second approach for resolving degeneracy is policy-based. We examine the sets of finite horizon and infinite horizon optimal decision sequences, without restrictions on the cardinality of these sets. Convergence of the finite horizon optimal sets to the infinite horizon optimal set implies convergence of their lexicographic minimum elements. This convergence leads to a simple algorithm for identifying an optimal initial decision by solving finite horizon problems, breaking ties for optimal by choosing the lexicographic minimum. Finally, we present "reachability" conditions under which set convergence takes place. In problems with regeneration point structure, we give a stopping rule guaranteed to settle on an optimal initial decision in finite time.