We consider a class of stochastic dynamic programming problems that are amenable to relaxation via decomposition. We compare two techniques under an additively separable value function approximation, namely Lagrangian relaxation and the linear programming (LP) approach to approximate dynamic programming. We prove that the linear programming-based approximate dynamic programming method achieves tighter bounds than the Lagrangian relaxation. We also investigate the gap between the two bounds, proving conditions under which both are tight, and providing an example in which the gap may be arbitrarily large. Algorithmically, we show how the computationally more complex LP can be solved using column generation. Computational results on several sets of problem instances show that the LP-based method results in better policies, and that the differences in the bounds depend on the nature of the underlying constraints being relaxed. We consider a class of stochastic dynamic programming problems that are amenable to relaxation via decomposition. We compare two techniques under an additively separable value function approximation, namely Lagrangian relaxation and the linear programming (LP) approach to approximate dynamic programming. We prove that the linear programming-based approximate dynamic programming method achieves tighter bounds than the Lagrangian relaxation. We also investigate the gap between the two bounds, proving conditions under which both are tight, and providing an example in which the gap may be arbitrarily large. Algorithmically, we show how the computationally more complex LP can be solved using column generation. Computational results on several sets of problem instances show that the LP-based method results in better policies, and that the differences in the bounds depend on the nature of the underlying constraints being relaxed.