We consider a broad class of stochastic dynamic programming problems that are amenable to relaxation via decomposition. These problems comprise multiple subproblems that are independent of each other except for a collection of coupling constraints on the action space. We fit an additively separable value function approximation using two techniques, namely, Lagrangian relaxation and the linear programming (LP) approach to approximate dynamic programming. We prove various results comparing the relaxations to each other and to the optimal problem value. We also provide a column generation algorithm for solving the LP-based relaxation to any desired optimality tolerance, and we report on numerical experiments on bandit-like problems. Our results provide insight into the complexity versus quality trade-off when choosing which of these relaxations to implement.  A classical result in integer programming, due to Geoffrion (1974), relates the optimal objective value of the Lagrangian dual with that of the linear programming (LP) relaxation. Consider an integer program that maximizes a linear objective function over linear constraints that can be divided into two groups: so-called "easy" constraints, and "complicating" constraints. The idea of Lagrangian relaxation is to dualize the complicating constraints with a penalty vector , i.e., add terms to the objective function penalizing constraint violations, and then optimize the resulting objective function over the remaining "easy" constraints. For any penalty vector, this gives an upper bound on the optimal objective value of the integer program, z IP . The Lagrangian dual minimizes over to find the smallest upper bound, z LD . A result of Geoffrion (1974) implies that where z LP is the optimal objective value of the LP relaxation of the integer program. This result provides an important justification for considering Lagrangian relaxations of integer programs, and Geoffrion's (1974) work paved the way for many papers (Fisher 1981 ) that used the Lagrangian approach. In recent years, there has been considerable research interest in solving stochastic dynamic optimization problems. Because static, deterministic special cases of these problems may indeed be integer programs, the class of stochastic dynamic optimization problems is at least as difficult to solve as the class of integer programs. Although dynamic optimization problems can in theory be solved using exact dynamic programming (Bellman 1957), this proves intractable for many problems in practice, due to the so-called "curse of dimensionality." Although the problems in this area are of significant practical interest, there is currently a scarcity of theory to guide the practitioner. Competing techniques abound, and practical dynamic optimization often requires problem-specific approaches. Various proposals have been made to break the curse, all of which fall under the heading of "approximate dynamic programming" methods. However, to date there is no result like (1) that compares relaxations. The purpose of this paper is to investigate an analogous result for two relaxations of a special class of such stochastic, dynamic optimization problems, called weakly coupled dynamic programs. 1 Such problems decompose into independent dynamic programs, or subproblems, except for a set of linking constraints on the actions. When these constraints bind weakly, we expect the relaxations to be close to the original problem. Hawkins (2003) describes many practical problems that fit this structure, including ones that arise in supply chain management, multiclass queueing networks, auctions, and others. Examples include: • Multiarmed and restless bandit problems. The restless bandit problem (Whittle 1988) is a classical resource 712
REF focus on stochastic dynamic programming problems that are suitable for relaxation via decomposition.
Relaxations of Weakly Coupled Stochastic Dynamic Programs
Oper. Res.
Oper. Res.
Computer Science Mathematics