On the Minimum Pair Approach for Average-Cost Markov Decision Processes with Countable Discrete Action Space and Strictly Unbounded Costs

Huizhen Yu

Published 2019-02-27Version 1

We consider average-cost Markov decision processes (MDPs) with Borel state space, countable, discrete action space, and strictly unbounded one-stage costs. For the minimum pair approach, we introduce a new majorization condition on the state transition stochastic kernel, in place of the commonly required continuity conditions on the MDP model. We combine this majorization condition with Lusin's theorem to prove the existence of a stationary minimum pair--that is, a stationary policy paired with an invariant probability measure it induces on the state space, with the property that the pair attains the minimal long-run average cost over all policies and initial distributions. We also establish other optimality properties of a stationary minimum pair, and for the stationary policy in such a pair, under additional recurrence or regularity conditions, we prove its pathwise optimality and strong optimality. Our results can be applied to a class of countable action space MDPs in which, with respect to the state variable, the dynamics and one-stage costs are discontinuous.