Efficient approximate linear programming for factored MDPs

doi:10.1016/j.ijar.2015.06.002

Return

Efficient approximate linear programming for factored MDPs

2015-08-01

DOI：10.1016/j.ijar.2015.06.002

Original

Save

View PDF

Abstract

En 中文

Factored Markov Decision Processes (MDPs) provide a compact representation for modeling sequential decision making problems with many variables. Approximate linear programming (LP) is a prominent method for solving factored MDPs. However, it cannot be applied to models with large treewidth due to the exponential number of constraints. This paper proposes a novel and efficient approximate method to represent the exponentially many constraints. We construct an augmented junction graph from the factored MDP, and represent the constraints using a set of cluster constraints and separator constraints, where the cluster constraints play the role of reducing the number of constraints, and the separator constraints enforce the consistency of neighboring clusters so as to improve the accuracy. In the case where the junction graph is tree-structured, our method provides an equivalent representation to the original constraints. In other cases, our method provides a good trade-off between computation and accuracy. Experimental results on different models show that our algorithm performs better than other approximate linear programming algorithms on computational cost or expected reward. (C) 2015 Elsevier Inc. All rights reserved.

Keywords:

Factored MDPs

Approximate linear programming

Junction graph

Cluster constraints

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.