Weakly Coupled Stochastic Dynamic Programs with Shared Signals

This dissertation studies approximation methods for a broad class of sequential decision problems comprised of separate sub-systems that are coupled by linking constraints as well as shared exogenous information (or ``signals"). Such problems arise in a variety of applications and can be formulated as stochastic dynamic programs (DPs), which in principal can be solved optimally through the corresponding Bellman equations. However, problems with such a structure suffer from the "curse of dimensionality," rendering a solution of the Bellman equations impractical unless the number of sub-systems is small. Thus, we focus on developing approximation methods that are computationally efficient and have strong performance guarantees in theory and practice.

In this dissertation, we first focus on upper bounds, which can serve as benchmarks to evaluate the performance of feasible policies. Two widely studied approximations of such problems are approximate linear programs (ALP) and Lagrangian relaxations. It is well-known that both approximations provide upper bounds on the optimal policy and that the ALP provides a tighter upper bound. However, the ALP relaxation is typically much harder to solve. We develop a framework to explicitly characterize the gap between the two approximations. Our results show that under mild conditions, the gap is bounded from above by a constant that is independent of the number of sub-systems; and the gap equals zero for several widely studied problems.

The second part of the dissertation focuses on analyzing the performance of feasible policies generated from Lagrangian relaxations, which involves relaxing the linking constraints and penalizing violations of the constraints with a Lagrangian penalty. However, even with the linking constraints relaxed, the shared signals induce correlation between the sub-systems and we need to choose the Lagrange multipliers carefully so that the generated policies achieve good performance. In particular, we develop a "special" Lagrangian relaxation and a DP formulation of the corresponding fluid relaxation, which can be solved by our iterative primal-dual algorithm. We then analyze the performance of the feasible dynamic fluid policy. Our analysis implies, under mild conditions, that the policy achieves asymptotic optimality as the number of sub-systems grows large. Finally, we demonstrate the results in two applications: (i) a dynamic capital budgeting problem and (ii) a multi-location inventory management problem with ``world-driven" demands.