Adaptive Random Forests from Online Learning and Testing by Betting

Adaptive Random Forests (ARF) are among the most effective ensemble methods for learning from non-stationary data streams, yet their success relies on heuristic drift detectors and reset rules that lack formal guarantees and require careful tuning. We revisit ARF from an online learning perspective and show that its design decomposes into two fundamental questions: how to aggregate a dynamically evolving set of trees, and how to update the pool of trees over time. We address aggregation using parameter-free online learning methods with strongly adaptive regret, enabling the ensemble to track the best tree mixture. For pool updates, we replace detector-driven resets with deterministic multi-scale scheduling based on geometric lifetimes, combined with incumbent--challenger replacement governed by anytime-valid statistical tests. This design yields theoretical guarantees: global control of false replacements, bounds on promotion delay under post-change advantage, and adaptivity under piece-wise stationary environment. Empirically, the resulting Online RF consistently outperforms ARF and is competitive with broader streaming baselines across several classification and regression benchmarks.