Self-Adapting Network Relaxations for Weakly Coupled Markov Decision Processes

Weakly coupled Markov decision processes (WDPs) arise in dynamic decision-making and reinforcement learning. These models are often high dimensional but decompose into smaller component MDPs when coupling constraints are relaxed. Lagrangian relaxations of WDPs that dualize linking constraints are commonly used to compute heuristic policies and (optimistic) bounds. While computationally appealing, this Lagrangian approach averages away combinatorial information embedded in the linking constraints. We present a class of network relaxations, dubbed feasibility network relaxations (FNRs), that embed an exact network encoding of the linking constraints into a linear programming flow model. We develop a procedure to obtain the minimally sized such relaxation, which we refer to as self-adapting FNR, as its size automatically adjusts to the structure of the linking constraints. We analyze this model to inform the approximation of WDPs: (i) self-adapting FNR provides (weakly) stronger bounds than standard Lagrangian relaxation and is polynomially sized for instances where the linking constraints admit a tractable network representation; and (ii) self-adapting FNR provides bounds and policies that match the approximate linear programming (ALP) approach but is substantially smaller in size, even polynomially sized when existing ALP formulations are exponentially large. We perform numerical experiments on constrained dynamic assortment and preemptive maintenance applications. Our results show that self-adapting FNR significantly improves on standard Lagrangian relaxation in terms of policy performance and/or bounds, although requiring more time, while being an order of magnitude faster than models based on alternative Lagrangian approaches and ALP, which are unsolvable in several instances