Learning Sorting and Decision Trees with POMDPs
Blai Bonet, Héctor Geffner · 1998
pomdps are general models of sequential decisions in which both actions and observations can be probabilistic. Many problems of interest can be formulated as pomdps, yet the use of pomdps has been limited by the lack of effective algorithms. Recently this has started to change and a number of problems such as robot navigation and planning are beginning to be formulated and solved as pomdps. The advantage of the pomdp approach is its clean semantics and its ability to produce principled solutions that integrate physical and information gathering actions. In this paper we pursue this approach in the context of two learning tasks: learning to sort a vector of numbers and learning decision trees from data. Both problems are formulated as pomdps and solved by a general pomdp algorithm. The main lessons and results are that 1) the use of suitable heuristics and representations allows for the solution of sorting and classification pomdps of non-trivial sizes, 2) the quality of the resulting...