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 possibly nonconvex set whose members are unique up to the 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 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.