Markov optimization problems: state-action frequencies revisited

The authors consider a controlled Markov chain with countable state and action spaces. The basic quantities which determine the values of average cost functionals are identified. Under some regularity conditions, these turn out to be the collection of numbers, one for each state-action pair, describing for each state the relative number of uses of each action. These conditional frequencies, which are defined pathwise, are shown to determine the state-action frequencies which, in the finite case, are known to determine the costs. This is extended to the countable case, allowing for unbounded costs. The space of frequencies is shown to be closed and convex, and the extreme points are identified with stationary deterministic policies. This immediately implies that for several optimization problems the search for optimality can be restricted to stationary policies. These problems include the standard Markov decision process, constrained optimization (both in terms of average cost functionals), and variability-sensitive optimization. An application to a queueing problem is given, where these results imply the existence of optimal stationary policies in constrained optimization problems