Sample Efficient Learning with Feature Selection for Factored MDPs

In reinforcement learning, state is often represented by feature vectors. Prior sample complexity bounds scale with the complexity of all features. However, not all features may be necessary for learning a good policy. Therefore it is of significant interest to understand if the sample complexity can scale with the complexity of necessary features instead of all features. We answer this in the affirmative for at least one important case of interest: factored Markov Decision Processes. We show that is possible to eliminate unnecessary features by using directed exploration and leveraging the negative information from failing to reach desired states. Under mild assumptions, this is sufficient to show there exists an RL algorithm whose sample complexity scales with the cardinality of the parent sets of the necessary features, rather than the parent sets of all features. This yields an exponential improvement in sample complexity bounds when the maximum cardinality of the parent sets of the necessary features is smaller than for all features.

Authors

• Zhaohan Guo
• Emma Brunskill Stanford University

Keywords

No keywords are indexed for this paper.