Optimality Inequalities for Average Cost Markov Decision Processes and the Stochastic Cash Balance Problem

Eugene A. Feinberg
Department of Applied Mathematics and Statistics
State University of New York at Stony Brook
Stony Brook, NY 11794-3600

Mark E. Lewis
School of Operations Research & Industrial Engineering
Cornell University
226 Rhodes Hall, Ithaca, NY 14853


For general state and action space Markov decision processes, we present sufficient conditions for
the existence of solutions of the average cost optimality inequalities. These conditions also imply the
convergence of both the optimal discounted cost value function and policies to the corresponding objects
for the average costs per unit time case. Inventory models are natural applications of our results. We
describe structural properties of average cost optimal policies for the cash balance problem; an inventory
control problem where the demand may be negative and the decision-maker can produce or scrap
inventory. We also show the convergence of optimal thresholds in the finite horizon case to those under
the expected discounted cost criterion and those under the expected discounted costs to those under the
average costs per unit time criterion.