Structure Aware Lagrangian Relaxations for Weakly Coupled Markov Decision Processes
Event details
| Date | 22.04.2024 |
| Hour | 14:00 |
| Speaker | Professor Selva Nadarajah |
| Location |
ODY 403
|
| Category | Conferences - Seminars |
| Event Language | French, English |
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 (LAG), which averages combinatorial information in the linking constraints, as well as approximate linear programming (ALP), which captures this information exactly, often with higher computational complexity. We introduce feasibility network relaxations (FNRs), a new class of structure-aware Lagrangian relaxations with multipliers based on an exact network flow representation of linking constraints. We develop a procedure to obtain the unique minimally sized relaxation, which we refer to as self-adapting FNR, as its size automatically adjusts to the structure of the linking constraints. Our analysis informs model selection: (i) the self-adapting FNR provides (weakly) stronger bounds than LAG, is polynomially sized when linking constraints admit a tractable network representation, and can even be smaller than LAG, and (ii) self-adapting FNR provides bounds and policies that match ALP but is substantially smaller in size than the ALP formulation and a recent alternative Lagrangian that is equivalent to ALP. We perform numerical experiments on constrained dynamic assortment and preemptive maintenance applications. Our results show that self-adapting FNR significantly improves upon LAG in terms of policy performance and/or bounds, while being an order of magnitude faster than an alternative Lagrangian and ALP, which are unsolvable in several instances. (Joint work with Andre Cire, University of Toronto; talk based on paper at this link forthcoming in Management Science and follow up work)
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.
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
- General public
- Free
Organizer
- Professor Daniel Kuhn
Contact
- Professor Daniel Kuhn