  Domain-specific features are important in representing problem structure
throughout machine learning and decision-theoretic planning. In planning, once
state features are provided, domain-independent algorithms such as approximate
value iteration can learn weighted combinations of those features that often
perform well as heuristic estimates of state value (e.g., distance to the
goal). Successful applications in real-world domains often require features
crafted by human experts. Here, we propose automatic processes for learning
useful domain-specific feature sets with little or no human intervention. Our
methods select and add features that describe state-space regions of high
inconsistency in the Bellman equation (statewise Bellman error) during
approximate value iteration. Our method can be applied using any
real-valued-feature hypothesis space and corresponding learning method for
selecting features from training sets of state-value pairs. We evaluate the
method with hypothesis spaces defined by both relational and propositional
feature languages, using nine probabilistic planning domains. We show that
approximate value iteration using a relational feature space performs at the
state-of-the-art in domain-independent stochastic relational planning. Our
method provides the first domain-independent approach that plays Tetris
successfully (without human-engineered features).
