Symmetric Approximate Linear Programming for Factored MDPs with Application to Constrained Problems
In Annals of Mathematics and Artificial Intelligence. Pages 273--293. 2006.Copyright © 2006 Springer. The original publication is available at www.springerlink.com: http:://dx.doi.org/10.1007/s10472-006-9038-x
Abstract
A weakness of classical Markov decision processes (MDPs) is that they scale very poorly due to the flat state-space representation. Factored MDPs address this representational problem by exploiting problem structure to specify the transition and reward functions of an MDP in a compact manner. However, in general, solutions to factored MDPs do not retain the structure and compactness of the problem representation, forcing approximate solutions, with approximate linear programming (ALP) emerging as a promising MDP-approximation technique. To date, most ALP work has focused on the primal-LP formulation, while the dual LP, which forms the basis for solving constrained Markov problems, has received much less attention. We show that a straightforward linear approximation of the dual optimization variables is problematic, because some of the required computations cannot be carried out efficiently. Nonetheless, we develop a composite approach that symmetrically approximates the primal and dual optimization variables (effectively approximating both the objective function and the feasible region of the LP), leading to a formulation that is computationally feasible and suitable for solving constrained MDPs. We empirically show that this new ALP formulation also performs well on unconstrained problems.
BibTex
@article{ dolgov06amai_ALP,
paperID = "AMAI-06",
author = "Dmitri A. Dolgov and Edmund H. Durfee",
title = "Symmetric Approximate Linear Programming for Factored MDPs with Application to Constrained Problems",
pages = "273--293",
year = "2006",
journal = "Annals of Mathematics and Artificial Intelligence"
}
Download:
[pdf]
[ps.gz]