An MILP-Based Solution Scheme for Factored Markov Decision Processes

Factored Markov decision processes (MDPs) are a prominent paradigm within the artificial intelligence community for modeling and solving large-scale MDPs whose rewards and dynamics decompose into smaller, loosely interacting components. Through the use of value function approximations, dynamic Bayesian networks, and context-specific independence, factored MDPs can achieve an exponential reduction in the state space of an MDP and, thus, scale to problem sizes that are beyond the reach of classical MDP algorithms. However, factored MDPs are typically solved using custom-designed algorithms that can require meticulous implementations and considerable fine-tuning. In this paper, we propose a mathematical programming approach to solving factored MDPs. Unlike existing solution schemes, our approach leverages off-the-shelf solvers, and this enables streamlined implementation and maintenance. Moreover, we exploit the factored structure in both state and action spaces, and we employ feature representations to unify existing methods, taking advantage of context-specific independence in problem classes that other approaches cannot solve efficiently. To further enhance scalability, we introduce a feature learning scheme that automatically identifies informative features and a dynamic basis approximation scheme that adaptively refines our value function approximations. Our numerical experiments demonstrate the potential of our approach.

Funding: H. Liu gratefully acknowledges funding from the National Natural Science Foundation of China [Grants 12301403, 72192830, and 72192832]. W. Wiesemann’s research is funded by the Engineering and Physical Sciences Research Council [Grant EP/W003317/1]. M.-C. Yue is supported in part by the Hong Kong Research Grants Council under the General Research Fund project [Grant 17309423].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2024.0934.