# Efficient Online Decision Tree Learning with Active Feature Acquisition

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 56 references that are in the map.
- First posted on arXiv 3 May 2023.

## Builds on (most cited first, 16 of 16)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Extremely Fast Decision Tree](https://mlsanity.com/paper/1802.08780/) (2018)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [Model-based Reinforcement Learning for Continuous Control with Posterior Sampling](https://mlsanity.com/paper/2012.09613/) (2020)
- [Random Forest for the Contextual Bandit Problem - extended version](https://mlsanity.com/paper/1504.06952/) (2015)
- [Near Optimal Bayesian Active Learning for Decision Making](https://mlsanity.com/paper/1402.5886/) (2014)
- [Efficient Online Learning for Optimizing Value of Information: Theory and Application to Interactive Troubleshooting](https://mlsanity.com/paper/1703.05452/) (2017)
- [Near-optimal Bayesian Active Learning with Correlated and Noisy Tests](https://mlsanity.com/paper/1605.07334/) (2016)
- [A Bit Better? Quantifying Information for Bandit Learning](https://mlsanity.com/paper/2102.09488/) (2021)
- [A Reinforcement Learning Approach to Online Learning of Decision Trees](https://mlsanity.com/paper/1507.06923/) (2015)
- [Design and implementation for automated network troubleshooting using data mining](https://mlsanity.com/paper/1506.00108/) (2015)

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

- [A Survey on Active Feature Acquisition Strategies](https://mlsanity.com/paper/2502.11067/) (2025)
- [Cost-Efficient Online Decision Making: A Combinatorial Multi-Armed Bandit Approach](https://mlsanity.com/paper/2308.10699/) (2023)

## Abstract (arXiv)

Constructing decision trees online is a classical machine learning problem. Existing works often assume that features are readily available for each incoming data point. However, in many real world applications, both feature values and the labels are unknown a priori and can only be obtained at a cost. For example, in medical diagnosis, doctors have to choose which tests to perform (i.e., making costly feature queries) on a patient in order to make a diagnosis decision (i.e., predicting labels). We provide a fresh perspective to tackle this practical challenge. Our framework consists of an active planning oracle embedded in an online learning scheme for which we investigate several information acquisition functions. Specifically, we employ a surrogate information acquisition function based on adaptive submodularity to actively query feature values with a minimal cost, while using a posterior sampling scheme to maintain a low regret for online prediction. We demonstrate the efficiency and effectiveness of our framework via extensive experiments on various real-world datasets. Our framework also naturally adapts to the challenging setting of online learning with concept drift and is shown to be competitive with baseline models while being more flexible.