  This paper provides conditions under which total-cost and average-cost Markov
decision processes (MDPs) can be reduced to discounted ones. Results are given
for transient total-cost MDPs with tran- sition rates whose values may be
greater than one, as well as for average-cost MDPs with transition
probabilities satisfying the condition that there is a state such that the
expected time to reach it is uniformly bounded for all initial states and
stationary policies. In particular, these reductions imply sufficient
conditions for the validity of optimality equations and the existence of
stationary optimal poli- cies for MDPs with undiscounted total cost and
average-cost criteria. When the state and action sets are finite, these
reductions lead to linear programming formulations and complexity estimates for
MDPs under the aforementioned criteria.
