# Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 29 May 2026.

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

- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Safe Testing](https://mlsanity.com/paper/1906.07801/) (2019)
- [River: machine learning for streaming data in Python](https://mlsanity.com/paper/2012.04740/) (2020)
- [Hypothesis testing with e-values](https://mlsanity.com/paper/2410.23614/) (2024)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Parameter-Free Online Convex Optimization with Sub-Exponential Noise](https://mlsanity.com/paper/1902.01500/) (2019)
- [Monitoring Risks in Test-Time Adaptation](https://mlsanity.com/paper/2507.08721/) (2025)
- [Adaptive XGBoost for Evolving Data Streams](https://mlsanity.com/paper/2005.07353/) (2020)
- [Are Ensembles Getting Better all the Time?](https://mlsanity.com/paper/2311.17885/) (2023)
- [Confidence Decision Trees via Online and Active Learning for Streaming (BIG) Data](https://mlsanity.com/paper/1604.03278/) (2016)
- [Test Martingales for bounded random variables](https://mlsanity.com/paper/1801.09418/) (2018)
- [Learning from Data Streams: An Overview and Update](https://mlsanity.com/paper/2212.14720/) (2022)
- [DriftMoE: A Mixture of Experts Approach to Handle Concept Drifts](https://mlsanity.com/paper/2507.18464/) (2025)

## Abstract (arXiv)

Bagging-based ensembles, most notably Adaptive Random Forests, are among the strongest performers for learning from data streams. A common denominator across these methods is their reliance on Hoeffding Trees as base learners, which grow decision trees incrementally by testing whether a candidate split is significantly better than its alternatives using concentration inequalities. Despite their empirical success, existing variants lack valid statistical guarantees. Current analyses rely on fixed-sample concentration bounds, while split decisions are made using data-dependent stopping rules, which invalidates their guarantees and can drive the probabilty of incorrect splits to one. We introduce a principled alternative based on anytime-valid inference. Our method provides: (i) anytime-valid control of false splits under arbitrary data streams, including non-stationary settings; (ii) finite commitment time under a predictive advantage; and (iii) under stationary i.i.d. data, risk is monotone decreasing and strictly improves at every split. Empirically, we evaluate both standalone trees and their use within Adaptive Random Forests on non-stationary streams. Our method improves performance while producing substantially smaller trees.