The Functional Equations of Undiscounted Markov Renewal Programming

This paper investigates the solutions to the functional equations that arise inter alia in Undiscounted Markov Renewal Programming. We show that the solution set is a connected, though possibily nonconvex set whose members are unique up to n* constants, characterize n* and show that some of these n* degrees of freedom are locally rather than globally independent.

Our results generalize those obtained in Romanovsky (Romanovsky, I. 1973. On the solvability of Bellman's functional equation for a Markovian decision process. J. Math. Anal. Appl. 42 485–498.) where another approach is followed for a special class of discrete time Markov Decision Processes. Basically our methods involve the set of randomized policies. We first study the sets of pure and randomized maximal-gain policies, as well as the set of states that are recurrent under some maximal-gain policy.