Convergence of Value Functions for Finite Horizon Markov Decision Processes with Constraints

This paper is concerned with finite horizon countable state Markov decision processes (MDPs) having an absorbing set as a constraint. Convergence of value iteration is discussed to investigate the asymptotic behavior of value functions as the time horizon tends to infinity. It turns out that the value function exhibits three different limiting behaviors according to the critical value lambda(*), the so-called generalized principal eigenvalue, of the associated ergodic problem. Specifically, we prove that (i) if lambda(*) <, then the value function converges to a solution to the corresponding stationary equation; (ii) if lambda(*)>, then, after a suitable normalization, it approaches a solution to the corresponding ergodic problem; (iii) if lambda(*) = 0, then it diverges to infinity with, at most, a logarithmic order. We employ this convergence result to examine qualitative properties of the optimal Markovian policy for a finite horizon MDP when the time horizon is sufficiently large.

Automated summary

This paper examines the asymptotic behavior of value functions for finite horizon countable state Markov decision processes with an absorbing set as a constraint. It is found that the value function exhibits three different limiting behaviors based on the critical value lambda(*), namely converging to a solution of the stationary equation, approaching a solution of the ergodic problem after normalization, or diverging to infinity at most with a logarithmic order. These results are used to investigate qualitative properties of the optimal Markovian policy for a finite horizon MDP with a sufficiently large time horizon.