Optimality Extension for Discounted Finite Markov Decision Processes

We present a new method called ''optimality extension'' to solve a finite discounted Markov decision process (MDP) for an interval of discount factors rather than a single one. Starting from a discount factor α ∈ [0, 1) at which the set of optimal policies D (α) is known, Algorithm 1 detects whether α is a point where the set of optimal policies changes, i.e., an irregular point. If not, then Algorithm 2 computes two numbers ℒ(α) and U (α) such that the optimality of D (α) is extended to the interval [ℒ(α), U (α)] ∩ [0, 1). Moreover, Algorithm 3 iterates Algorithms 1 and 2 to approximate irregular points adjacent to a regular point.