Symmetric approximate linear programming for factored MDPs with application to constrained problems |
| |
Authors: | Dmitri A Dolgov Edmund H Durfee |
| |
Affiliation: | (1) Technical Research Department (AI & Robotics Group), Toyota Technical Center, 2350 Green Road, Ann Arbor, MI 48105, USA;(2) Electrical Engineering and Computer Science, University of Michigan, 2260 Hayward St., Ann Arbor, MI 48109, USA |
| |
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.
|
| |
Keywords: | Markov decision processes approximate linear programming primal-LP formulation dual LP constrained Markov problems |
本文献已被 SpringerLink 等数据库收录! |
|