Practical Feature Selection for Online Reinforcement Learning and Planning in Relational MDPs

Planning problems with large state spaces and unknown models can be solved by value-based reinforcement learning methods, using function approximation which abstracts states with feature vectors. Sample complexity increases when unnecessary features are selected. Conversely, omitting necessary features results in poor performances. A feature selection algorithm should add all necessary features while avoiding unnecessary ones. We introduce an online feature selection that considers the structure of relational MDPs (RMDPs) to reduce unnecessary features. Generalisation over different planning problems can be achieved by representing the approximated value-function with lifted representations of state variables and actions. Empirical results show that our method is practical for solving large RMDPs with reduced sample complexities and can generalise over different problems.