An MILP-based solution scheme for factored Markov decision processes
File(s)
Accepted version
Author(s)
Liu, Huikang
Wiesemann, Wolfram
Yue, Man-Chung
Type
Journal Article
Abstract
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, which 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 while 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.
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, which 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 while 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.
Date Issued
2026-07-06
Date Acceptance
2026-05-04
Citation
Operations Research, 2026
ISSN
0030-364X
Publisher
Institute for Operations Research and Management Sciences
Journal / Book Title
Operations Research
Copyright Statement
SubjeCopyright © 2026, INFORMS. This is the author’s accepted manuscript made available under a CC-BY licence in accordance with Imperial’s Research Publications Open Access policy (www.imperial.ac.uk/oa-policy)
License URL
Publication Status
Published online
Date Publish Online
2026-07-06