Selvaprabu Nadarajah, Self-Adapting Network Relaxations for Weakly Coupled Markov Decision Processes
137 بار بازدید -
11 ماه پیش
-
Part of Discrete Optimization Talks:
Part of Discrete Optimization Talks: https://talks.discreteopt.com
Selvaprabu Nadarajah - University of Illinois-Chicago
Speaker webpage: https://selvan.people.uic.edu/
Self-Adapting Network Relaxations for Weakly Coupled Markov Decision Processes
Abstract: High-dimensional weakly coupled Markov decision processes (WDPs) arise in dynamic decision making and reinforcement learning, decomposing into smaller MDPs when linking constraints are relaxed. The Lagrangian relaxation of WDPs (LAG) exploits this property to compute policies and (optimistic) bounds efficiently; however, dualizing linking constraints averages away combinatorial information. We introduce feasibility network relaxations (FNRs), a new class of linear programming relaxations that exactly represents the 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 the approximate linear programming (ALP) approach 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).
Link to paper: https://papers.ssrn.com/sol3/papers.c...
Bio: Selva Nadarajah is an Associate Professor of Information and Decision Sciences at the University of Illinois Chicago (UIC) College of Business. His research addresses challenges at the interface of operations and finance arising in the energy industry using reinforcement learning and optimization. His recent work develops self-adapting approaches, which are optimization methods and formulations that are capable of automatically adapting themselves to instance-specific information in a problem class or information arriving over time. Selva has received 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, the 2014 William L. Cooper Dissertation Award, and the 2013 Egon Balas Best Student Paper Award. Selva completed his PhD in Operations Research at the Tepper School of Business in Carnegie Mellon University.
Selvaprabu Nadarajah - University of Illinois-Chicago
Speaker webpage: https://selvan.people.uic.edu/
Self-Adapting Network Relaxations for Weakly Coupled Markov Decision Processes
Abstract: High-dimensional weakly coupled Markov decision processes (WDPs) arise in dynamic decision making and reinforcement learning, decomposing into smaller MDPs when linking constraints are relaxed. The Lagrangian relaxation of WDPs (LAG) exploits this property to compute policies and (optimistic) bounds efficiently; however, dualizing linking constraints averages away combinatorial information. We introduce feasibility network relaxations (FNRs), a new class of linear programming relaxations that exactly represents the 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 the approximate linear programming (ALP) approach 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).
Link to paper: https://papers.ssrn.com/sol3/papers.c...
Bio: Selva Nadarajah is an Associate Professor of Information and Decision Sciences at the University of Illinois Chicago (UIC) College of Business. His research addresses challenges at the interface of operations and finance arising in the energy industry using reinforcement learning and optimization. His recent work develops self-adapting approaches, which are optimization methods and formulations that are capable of automatically adapting themselves to instance-specific information in a problem class or information arriving over time. Selva has received 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, the 2014 William L. Cooper Dissertation Award, and the 2013 Egon Balas Best Student Paper Award. Selva completed his PhD in Operations Research at the Tepper School of Business in Carnegie Mellon University.
11 ماه پیش
در تاریخ 1402/07/19 منتشر شده
است.
137
بـار بازدید شده