An MILP-Based Solution Scheme for Factored Markov Decision Processes
- 1 September 2026
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 74 (5) , 2728-2747
Abstract
Off-the-Shelf Solvers Take on the Curse of Dimensionality Many real-world decision problems—from managing power plants and microgrids to coordinating fleets of robots, recommender systems, and traffic networks—involve dynamics and rewards that decompose into smaller, loosely interacting components. Factored Markov decision processes (FMDPs) exploit this structure to escape the curse of dimensionality, but they have traditionally been solved with bespoke algorithms that require painstaking implementation and substantial fine-tuning. In this issue, Liu, Wiesemann, and Yue introduce a new mathematical programming perspective on FMDPs that swaps hand-crafted machinery for off-the-shelf optimization solvers. By encoding sparse dependencies through mixed-integer linear programming–representable feature vectors, their formulation exploits factored structure in both states and actions, unifies and extends existing treatments of context-specific independence, and pairs an approximate linear program with a novel cutting-plane algorithm. Companion feature-learning and dynamic-basis routines further enhance scalability, and computational experiments across stylized and operational case studies illustrate the method’s promise.Keywords
This publication has 23 references indexed in Scilit:
- Factored MDPs for Optimal Prosumer Decision-Making in Continuous State Spaces2016
- Approximate Dynamic Programming2011
- Efficient solutions to factored MDPs with imprecise transition probabilitiesArtificial Intelligence, 2011
- An Intelligent Assistant for Power Plants Based on Factored MDPs2009
- Biconvex sets and optimization with biconvex functions: a survey and extensionsMathematical Methods of Operations Research, 2007
- Power Plant Operator Assistant: An Industrial Application of Factored MDPsLecture Notes in Computer Science, 2004
- Stochastic dynamic programming with factored representationsArtificial Intelligence, 2000
- Markov Decision Processes1994
- Generalized polynomial approximations in Markovian decision processesJournal of Mathematical Analysis and Applications, 1985
- On the Theory of Dynamic ProgrammingProceedings of the National Academy of Sciences, 1952