Information Relaxation Bounds for Infinite Horizon Markov Decision Processes

We consider infinite horizon stochastic dynamic programs with discounted costs and study how to use information relaxations to calculate lower bounds on the performance of an optimal policy. We develop a general framework that allows for reformulations of the underlying state transition function. These reformulations can simplify the information relaxation calculations, both in leading to finite horizon subproblems and by reducing the number of states in these subproblems. We study as important special cases both “weak formulations ” in which states are independent of actions and “strong formulations” which retain the original dependence on actions. Our reformulations incorporate penalties for information in a direct way via control variate terms. We show that the approach improves on the lower bounds from “Bellman feasible ” approximate value functions when the control variates are built from these approximate value functions. We apply the approach to the problem of dynamic service allocation in a multiclass queue; such models are well-studied but challenging to solve. In our examples, we find the information relaxation lower bounds are relatively easy to calculate and are very close to the upper bounds obtained from simple heuristics. Finally, we discuss extensions of the approach to stochastic shortest path and average cost problems