"Function approximation" is the key component to deal with the potentially too large state space (virtually infinite, considering there are real-valued features). Last year (http://www-cse.ucsd.edu/~elkan/254spring01/), Sameer talked about reinforcement learning applied to the game Othello, and a neural network was used as function approximator, to avoid the combinatorial explosion of states. I think the multivariate linear regression tree in ProbE performs a similar task. The tree can have nodes like "income < $30K", etc. and the system doesn't need to spend states for all values of feature "income".