Sample Efficient Feature Selection for Factored MDPs

2017/03/09 by Zhaohan Daniel Guo, Emma Brunskill, Guo, Zhaohan Daniel +1 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1703.03454

openalex publication_date 2017/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Playing Atari with Deep Reinforcement Learning

Cited by

• Where to Intervene: Action Selection in Deep Reinforcement Learning

Related

• Feature Selection Using Reinforcement Learning
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• Efficient Reinforced Feature Selection via Early Stopping Traverse Strategy
• Automation and Feature Selection Enhancement with Reinforcement Learning (RL)
• Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles