Towards Exploiting Duality in Approximate Linear Programming for MDPs

Abstract

A weakness of classical methods for solving Markov decision processes is that they scale very poorly because of the flat state space, which subjects them to the curse of dimensionality. Fortunately, many MDPs are well-structured, which makes it possible to avoid enumerating the state space. To this end, factored MDP representations have been proposed (Boutilier, Dearden, & Goldszmidt 1995; Koller & Parr 1999) that model the state space as a cross product of state features, represent the transition function as a Bayesian network, and assume the rewards can be expressed as sums of compact functions of the state features. A challenge in creating algorithms for the factored representations is that well-structured problems do not always lead to compact and well-structured solutions (Koller & Parr 1999); that is, an optimal policy does not, in general, retain