An MILP-Based Solution Scheme for Factored Markov Decision Processes

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.