Sample Efficient Feature Selection for Factored MDPs
This addresses the challenge of high sample complexity in reinforcement learning for real-world tasks with irrelevant features, though it is incremental as it builds on existing factored MDP frameworks.
The paper tackles the problem of sample-efficient feature selection in factored Markov Decision Processes by proposing the FS-EE algorithm, which automatically selects necessary features and achieves sample complexity scaling with the in-degree of only those features, potentially leading to significant reductions compared to using all features.
In reinforcement learning, the state of the real world is often represented by feature vectors. However, not all of the features may be pertinent for solving the current task. We propose Feature Selection Explore and Exploit (FS-EE), an algorithm that automatically selects the necessary features while learning a Factored Markov Decision Process, and prove that under mild assumptions, its sample complexity scales with the in-degree of the dynamics of just the necessary features, rather than the in-degree of all features. This can result in a much better sample complexity when the in-degree of the necessary features is smaller than the in-degree of all features.