# Sample Efficient Feature Selection for Factored MDPs

arXiv: https://arxiv.org/abs/1703.03454 · HTML: https://mlsanity.com/paper/1703.03454/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2017.

## Built on by (most cited first, 5 of 5)

- [Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information](https://mlsanity.com/paper/2206.04282/) (2022)
- [Sequential Knockoffs for Variable Selection in Reinforcement Learning](https://mlsanity.com/paper/2303.14281/) (2023)
- [Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2310.07518/) (2023)
- [Off-policy Evaluation with Deeply-abstracted States](https://mlsanity.com/paper/2406.19531/) (2024)
- [Where to Intervene: Action Selection in Deep Reinforcement Learning](https://mlsanity.com/paper/2507.04187/) (2025)

## Abstract (arXiv)

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.