Structure Aware Lagrangian Relaxations with Approximation Guarantees for Weakly Coupled Markov Decision Processes
Abstract: Weakly coupled Markov decision processes represent a structured class of stochastic decision models that couple component Markov decision processes via linking constraints, and arise in resource allocation, project selection, and scheduling problems. They are approximated using Lagrangian relaxation, which averages combinatorial information in the linking constraints, as well as fluid models and approximate linear programming, which capture this information exactly, often with higher computational complexity. We introduce structure-aware Lagrangian relaxations, a hierarchy of models that contains these two extremes studied in the literature, and unexplored models in between. We construct this hierarchy by taking a novel polyhedral perspective towards the representation of combinatorial structure of linking constraints. We prove a transferability result that ports integrality ratio guarantees of combinatorial systems to approximation guarantees on the optimal policy upper bound of models in our hierarchy with respect to the best model. For the broad class of packing problems, we show that model size depends exponentially and polynomially on the number of components when coupling constraints are represented exactly and approximately, respectively, a striking difference that supports finding models of small size with good performance in our hierarchy. For resource allocation problems, we numerically observe that structure-aware Lagrangian relaxations with bounds and policies comparable to existing models are orders of magnitude smaller in size, allowing us to improve the standard Lagrangian for previously intractable instances. (Joint work with Andre Cire, University of Toronto; talk based on paper at this link forthcoming in Management Science and follow up work)
Bio sketch: Selva Nadarajah is an Associate Professor of Information and Decision Sciences at the University of Illinois Chicago (UIC) College of Business and the Decision Intelligence R&D Lead at the Discovery Partners Institute (Innovation Hub of the University of Illinois System). He is also Guest Faculty at Argonne National Laboratories. Selva develops dynamic valuation and decision-making models that guide investment, operations, and risk management, with a focus on the energy industry. His ongoing energy projects study the effect of limited market data on NetZero planning and the consideration of social/equity risks. Selva also develops self-adapting stochastic optimization and reinforcement learning methods that endogenize model reformulation, performance acceleration, and parameter selection, with the goal of making these tools accessible to non-technical experts, drawing inspiration from commercial deterministic optimization solvers. Selva's research has been recognized with the 2021 Commodity and Energy Markets Association (CEMA) Best Paper Award, the 2020 INFORMS ENRE Young Researcher Prize, the Best Overall Paper at the 2020 NeurIPS Workshop on Tackling Climate Change with Machine Learning, and the 2014 William L. Cooper Dissertation Award.
Bio sketch: Selva Nadarajah is an Associate Professor of Information and Decision Sciences at the University of Illinois Chicago (UIC) College of Business and the Decision Intelligence R&D Lead at the Discovery Partners Institute (Innovation Hub of the University of Illinois System). He is also Guest Faculty at Argonne National Laboratories. Selva develops dynamic valuation and decision-making models that guide investment, operations, and risk management, with a focus on the energy industry. His ongoing energy projects study the effect of limited market data on NetZero planning and the consideration of social/equity risks. Selva also develops self-adapting stochastic optimization and reinforcement learning methods that endogenize model reformulation, performance acceleration, and parameter selection, with the goal of making these tools accessible to non-technical experts, drawing inspiration from commercial deterministic optimization solvers. Selva's research has been recognized with the 2021 Commodity and Energy Markets Association (CEMA) Best Paper Award, the 2020 INFORMS ENRE Young Researcher Prize, the Best Overall Paper at the 2020 NeurIPS Workshop on Tackling Climate Change with Machine Learning, and the 2014 William L. Cooper Dissertation Award.
Practical information
- Informed public
- Registration required
Organizer
- Prof. Daniel Kuhn