An MILP-Based Solution Scheme for Factored Markov Decision Processes

• 成果类型: Article; Early Access
• 署名作者: Liu, Huikang; Wiesemann, Wolfram; Yue, Man-Chung
• 署名单位: Shanghai Jiao Tong University; Imperial College London; Hong Kong Polytechnic University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.0934
• 发表日期: 2026
• 关键词: Optimization; approximations; algorithms

摘要

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.