1 Introduction↩︎

In streaming environments, where data arrive sequentially and models must be updated online, ensemble methods have emerged as the dominant paradigm. In particular, bagging-based approaches such as Adaptive Random Forests (ARF) [1], along with related variants including Streaming Random Patches [2], and K-Nearest Leaves [3], consistently rank among the top performers on recent benchmarks [4]–[6]. Among these, ARF has effectively become the de facto standard for ensemble learning in data streams, across both classification [7] and regression [1].

A striking commonality across these methods is their universal reliance on the Hoeffding Tree (HT), also known as the Very Fast Decision Tree (VFDT) [8], as the fundamental base learner. Despite its empirical success and wide adoption, the statistical foundation of the Hoeffding Tree is not valid. The HT’s core idea is to grow tree incrementally: at each node, it tests if sufficient data has arrived to commit to a split. The original algorithm invalidly applied Hoeffding’s inequality to non-linear impurity measures (e.g., Gini index). Subsequent corrections either substituted linear measures (e.g., misclassification error) [9] or applied more general bounds like McDiarmid’s inequality [10]–[12].

We argue that these fixes remain statistically invalid. All existing approaches overlook a fundamental issue: standard concentration inequalities assume a fixed sample size, yet the HT algorithm employs a data-dependent stopping rule. This phenomenon, known as optional continuation [13], [14], invalidates the guarantees of fixed-time concentration inequality. In particular, the probability of a false split can inflate to one (see Fig. 1 in [15]).

To resolve this, we abandon fixed-sample-size inequalities and instead leverage recent advances in sequential testing, specifically the safe, anytime-valid inference (SAVI) framework [16]–[22]. This paradigm is inherently robust to optional stopping.

Our main contributions are:

1. We derive a split criterion that remains valid under arbitrary data-dependent stopping rules. Our method controls false split decisions simultaneously over the entire lifetime of the tree, and applies to non-stationary and dependent data streams. When a candidate split exhibits a persistent predictive advantage, our procedure commits to the split in finite time.

2. Under stationarity, the learned tree’s expected loss is non-increasing over time, and improves monotonically as data accumulate.

3. We validate our method across several non-stationary environments, both as a standalone replacement for Hoeffding Trees and as a drop-in substitute within Adaptive Random Forests. The resulting ensemble of trees achieve higher predictive performance while being consistently smaller in depth or number of nodes.

2 Problem Definition↩︎

Let \((\mathcal{F}_t)_{t\ge0}\) be the filtration representing all information available up to time \(t\), including the data and any internal randomization: \(\mathcal{F}_t := \sigma((X_1,Y_1),\dots,(X_t,Y_t),U)\) where \(U\) denotes algorithmic randomness (if any). A quantity chosen at time \(t\) is predictable if it is \(\mathcal{F}_{t-1}\)-measurable.

For clarity, we present the problem for classification decision trees with binary splits on continuous features; extensions to multiway splits, categorical features, and regression follow by standard adaptations [23]. Each leaf node update mechanism has two components: (i) a split measure quantifying split quality, and (ii) a split condition determining whether the node should be partitioned.

A decision tree recursively partitions the input space \(\mathcal{X}\subseteq\mathbb{R}^d\) into a collection of axis-aligned regions. Each node \(v\) corresponds to a measurable region \(R(v)\subseteq\mathcal{X}\). A split candidate is a pair \(c=(j,s)\) with feature index \(j\in[d]\) and threshold \(s\in\mathbb{R}\), inducing child regions \[R(v_L^c)=R(v)\cap\{x_j\le s\}, \qquad R(v_R^c)=R(v)\cap\{x_j> s\}.\] At each node \(v\), the set of admissible splits is restricted to a finite candidate class \(C_v \subseteq \{1,\dots,d\}\times\mathbb{R}\). The finiteness of \(C_v\) reflects practical implementations (e.g., discretised thresholds, quantiles) and ensures that optimality is always defined with respect to a fixed, finite hypothesis class.

2.0.0.1 Batch decision tree learning.

Given a fixed dataset \(\mathcal{D}_t=\{(X_i,Y_i)\}_{i=1}^t\), an effective split maximally reduces node impurity. Define the samples reaching node \(v\) as \(A_t(v) := \{(X_i,Y_i)\in\mathcal{D}_t:X_i\in R(v)\}\), \(n_t(v) := |A_t(v)|\). Let \(p_t(v)\) denote the empirical class proportions, with components \(p_{t,k}(v) = \frac{1}{n_t(v)} \sum_{(X_i,Y_i)\in A_t(v)} \mathbb{1}\{Y_i=k\}.\) Common impurity measures \(\mathcal{I}(\cdot)\) include entropy and the Gini index: \(\mathcal{ I}_{\mathrm{entropy}}( p) = -\sum_k p_k\log \mathbf{p}_k,\) and \(\mathcal{I}_{\mathrm{Gini}}( p) = \sum_k p_k \bigl(1- p_k\bigr).\) For a candidate split \(c=(j,s)\in C_v\), the empirical impurity decrease at node \(v\) is \[\Delta_t^{v,c} = \mathcal{I}(\mathbf{p}_t(v)) - P_{t,L}\, \mathcal{I}(\mathbf{p}_t(v_{c}^L)) - P_{t,R}\, \mathcal{I}(\mathbf{p}_t(v_{c}^R)),\] where \(P_{t,L}=n_t(v_{c}^L)/n_t(v),\) and \(P_{t,R}=n_t(v_{c}^R)|/n_t(v).\)

In batch learning, the split at node \(v\) is chosen by maximising the empirical impurity reduction over the candidate set \(c^\star = \arg\max_{c\in C_v} \Delta_t^{v,c}.\)

2.0.0.2 Online decision tree learning.

In a streaming setting, observations \((X_t,Y_t)_{t\ge1}\) arrive sequentially and the dataset is never fully observed. The batch procedure is therefore inapplicable; instead, the learner must decide online when sufficient evidence justifies a split.

For each node \(v\) and split \(c\in C_v\), define the population impurity decrease as \[\Delta^{v,c} = \mathcal{I}( p(v)) - P_L\, \mathcal{I}( p(v_{c}^L)) - P_R\, \mathcal{I}( p(v_{c}^R)), \label{eq:pop95impurity}\tag{1}\] where probabilities correspond to their population counterparts under the data-generating distribution. Ideally, the learner would select a split \(c^\star\) satisfying \[\Delta^{v,c^\star} > \Delta^{v,c^\prime} \qquad \forall c^\prime \in C_v, \label{eq:pop95split}\tag{2}\] that is, the empirically chosen split coincides with the population-optimal one over the same finite candidate class.

Since \(\Delta^{v,c}\) is unknown, online algorithms rely on statistical inference from empirical estimates \(\Delta_t^{v,c}\) computed from the data observed so far. A common strategy introduces a threshold \(\varepsilon(n_t(v),\delta)\) such that, if \[\Delta_t^{v,c^\star} - \Delta_t^{v,c^\prime} > \varepsilon(n_t(v),\delta) \quad \forall c^\prime\in C_v,\] then, with probability at least \(1-\delta\), the selected split is population-optimal.

Hoeffding Trees [8] instantiate \(\varepsilon(\cdot)\) using Hoeffding’s inequality, despite the non-linearity of impurity criteria. Subsequent work replaces this with McDiarmid-type bounds [10]–[12] or linearized impurity measures [9].

2.0.0.3 The overlooked issue.

All existing guarantees are valid given a fixed sample size. In practice, however, impurity estimates are updated sequentially, and the algorithm commits to a split at the first time the stopping condition is satisfied. This induces a data-dependent stopping time that depends on the entire data trajectory.

Let \((C_t)_{t\ge1}\) be a sequence of confidence intervals for a parameter \(\delta\), constructed using a classical concentration inequality (e.g., Hoeffding’s inequality). Such bounds provide only fixed-time control: for any fixed \(t\), \[\mathbb{P}(\delta \notin C_t)\le \alpha,\] which offers no guarantee under data-dependent stopping. Instead, we require anytime-valid coverage: \[\mathbb{P}\!\left(\exists t\ge1:\delta \notin C_t\right)\le\alpha, \quad\text{or}\quad \mathbb{P}\!\left(\forall t\ge1:\delta \in C_t\right)\ge 1-\alpha.\] This immediately implies validity at any (possibly infinite) stopping time \(\tau\): \[\mathbb{P}(\delta \notin C_\tau)\le\alpha, \qquad \mathbb{P}(\delta \in C_\tau)\ge 1-\alpha.\]

Standard bounds fail under optional stopping (see Fig. 1 in [15]) and therefore do not control the probability of selecting an incorrect split at the time the algorithm actually stops.

Moreover, a fundamental gap exists between theory and practice. Classical Hoeffding-based analyses assume independent observations, yet Hoeffding Trees are most often deployed inside ensemble methods such as Adaptive Random Forests, which operate on non-stationary and potentially dependent streams. This directly violates the assumptions underlying existing guarantees. These observations motivate our central question:

3 Valid Sequential Tests for Split Selection↩︎

Our approach departs from the classical objective of selecting the split that maximizes population impurity reduction (cf. 2 ). In non-stationary environments, the population impurity 1 may itself be ill-defined, since the data-generating distribution may evolve over time and the optimal split may change accordingly. Rather than comparing candidate splits against each other under a static distribution, we instead ask a different question:

This reframes split selection as an online model comparison problem. Specifically, we compare two predictors: an incumbent model corresponding to the unsplit leaf, and a challenger model obtained by applying a candidate split. The goal is to determine, using accumulated information up to time \(t\), whether the challenger has achieved better predictive performance than the incumbent under potentially non-stationary and dependent data.

Predictive performance is evaluated using a loss function \(\ell\), with log loss and Brier score serving as loss-based analogues of entropy and Gini impurity. Our theoretical analysis assumes bounded losses \(\ell\in[0,1]\); when this condition does not hold in practice, we enforce it via normalization.

3.1 Testing a Candidate Split↩︎

Fix a leaf node \(v\) created at time \(s^v\). Until a split is committed, node \(v\) acts as the incumbent predictor.

At time \(s^v\), the learner selects a candidate split \(c\in C_v\). This defines a hypothetical challenger model that partitions \(R(v)\) into two child regions. No structural changes are made at this stage: the challenger is evaluated in shadow mode and does not affect future routing decisions.

• Incumbent \(m^{v}\) predicts using the empirical label distribution at node \(v\), estimated from data observed up to the current time.

• Challenger \(m^{v_c}\) identical to the incumbent, except that node \(v\) is split according to \(c\), with each child maintaining its own empirical label distribution.

For each \(t\ge s^v+1\),

1. Both predictors output prequential predictions based on \(\mathcal{F}_{t-1}\). \[\begin{align} m^{v}_{t-1}(x) &= p_{t-1}(v), \qquad x\in R(v), \nonumber\\ m^{v_{c}}_{t-1}(x) &= \begin{cases} p_{t-1}(v_{c}^L), & x\in R(v_{c}^L),\\[2mm] p_{t-1}(v_{c}^R), & x\in R(v_{c}^R), \end{cases} \end{align}\]

2. After observing \(Y_t\), we compute the losses and define the bounded difference \[\Delta_t^{v,c} := \ell\!\left(m^v_{t-1}(X_t),Y_t\right) - \ell\!\left(m^{v_{c}}_{t-1}(X_t),Y_t\right) \in[-1,1].\]

3. Both predictors are updated identically using \((X_t,Y_t)\); their only distinction remains the proposed split.

Since both predictions are \(\mathcal{F}_{t-1}\)-measurable, the conditional mean is well defined: \[\delta_t^{v,c} := \mathbb{E}\!\left[ \Delta_t^{v,c} \mid \mathcal{F}_{t-1} \right].\]

3.1.0.1 Defining improvement.

In non-stationary environments, there are two standard hypothesis-testing formulations for comparing predictive models over time [24]–[26], rosenbaum1995?.

The first formulation tests whether a challenger ever attains an advantage over the incumbent. This corresponds to the strong null hypothesis [26]: \[H_{0}^{v,c}: \qquad \forall t\ge s^v+1, \quad \delta_t^{v,c} \le 0.\] Under this hypothesis, the challenger is assumed to never outperform the incumbent at any point in time.

The second formulation evaluates whether the challenger improves upon the incumbent on average over time. This leads to the weak null hypothesis: \[H^{v,c}_{\mathrm{w},0}: \qquad \forall t\ge s^v+1, \quad \frac{1}{t- s^v} \sum_{u= s^v+1}^{t} \delta_u^{v,c} \le 0.\]

The choice between these formulations depends on the specific application. Recent work  [26] suggests using the strong null when comparing closely related algorithms operating on the same data stream, and the weak null when comparing substantially different models.

3.1.0.2 Choice in our setting.

We adopt the strong null (\(H_0^{v,c}\)) as our primary testing target. This aligns with the recommendation of [26] to use the strong null when comparing closely related algorithms trained on the same data. Indeed, during the test period, both models are trained using the same data and are directly related by construction. Empirically, we also found that the weak null leads to more conservative behaviour: splits are committed later, resulting in inferior predictive performance. This is expected, since the weak formulation relies on averaged effects that can be influenced by accumulated history.

For completeness, we derive sequential tests for both hypotheses. For notational brevity, we omit the superscripts \((v,c)\) where the context is unambiguous.

3.2 Anytime-Valid Test via Testing by Betting↩︎

We adopt the testing-by-betting framework [16]–[22], which interprets statistical hypothesis testing as a betting game against the null hypothesis. At each time step, the bettor wagers on whether the challenger outperforms the incumbent, as measured by the sign of \(\Delta_t\). Under the null hypothesis \(H_0\), no betting strategy can achieve positive expected growth. Under the alternative, the bettor’s wealth increases over time.

3.2.0.1 Testing by betting.

The bettor starts with unit wealth \(W_{s}=1\). At each time \(t\ge s + 1\), a predictable betting fraction \(\beta_t\in[0,1]\) is chosen based on \(\mathcal{F}_{t-1}\). After observing \(\Delta_t\), wealth is updated according to \[W_t = W_{t-1}\bigl(1+\beta_t \Delta_t\bigr). \label{eq:wealth95update95main}\tag{3}\] Since under the strong null \(H_0\) we have \(\mathbb{E}[\Delta_t\mid\mathcal{F}_{t-1}]\le 0\), the process \((W_t)_{t\ge s}\) is a nonnegative supermartingale.

By Ville’s inequality, for any \(\alpha\in(0,1)\), \[\mathbb{P}_{H_0}\!\left( \sup_{t\ge s } W_t \ge \frac{1}{\alpha} \right) \le \alpha.\] Consequently, thresholding the wealth process yields an anytime-valid test: regardless of the betting strategy, under \(H_0\) the wealth exceeds \(1/\alpha\) with probability at most \(\alpha\). Therefore, a wealth above this threshold is a strong evidence that the null is false.

3.2.0.2 Portfolio interpretation.

Following [20], we can equivalently represent the betting game as an online portfolio selection with two stocks. Define two assets with returns \[R_t^{(0)} := 1, \qquad R_t^{(1)} := 1+\Delta_t \in [0,2].\] Investing a fraction \(\beta_t\) in asset 1 and \(1-\beta_t\) in asset 0 yields gross return \[(1-\beta_t)R_t^{(0)} + \beta_t R_t^{(1)} = 1+\beta_t\Delta_t,\] which coincides with 3 one step’s update. Designing a powerful anytime-valid test therefore reduces to selecting an effective online portfolio strategy.

Rather than tuning \(\beta_t\), we adopt a parameter-free strategy: the Universal Portfolio (UP). UP is minimax-optimal with respect to the best constant rebalanced portfolio and, in i.i.d.markets, achieves the optimal growth rate of any fixed strategy [27]. UP constructs a mixture over constant rebalanced portfolios using a Jeffreys prior.

Concretely, we define \[\beta_t := \frac{ \int_0^1 \beta \prod_{u=s}^{t-1} \bigl(1+\beta\,\Delta_u\bigr) \,dF_+(\beta) }{ \int_0^1 \prod_{u=s}^{t-1} \bigl(1+\beta\,\Delta_u\bigr) \,dF_+(\beta) }, \; F_+ = \mathrm{Beta}\!\left(\tfrac12,\tfrac12\right), \label{eq:UP95beta}\tag{4}\] and update wealth via 3 . The resulting process remains a nonnegative supermartingale under \(H_0\) and empirically accumulates evidence rapidly when the challenger is superior.

3.2.0.3 Replacement rule and global error control.

We run one such test for each candidate split available at a leaf. Given per-test significance levels \(\alpha^{v, c}\), we replace the incumbent with the challenger at the stopping time \[\tau^{v,c} := \inf\!\left\{ t\ge s^v + 1: W^{v,c}_t \ge \frac{1}{\alpha^{v, c}} \right\}.\] We show in the next section that it yields global control: with probability at least \(1-\alpha\), no false replacement ever occurs over the entire stream. When multiple candidates cross their thresholds simultaneously, we select the one with the largest wealth.

3.3 Anytime-Valid Test via Confidence Sequences↩︎

The weak null hypothesis can be tested in a closely related manner using confidence sequences (CS). Let \((L_t,U_t)_{t\ge s^v +1}\) be a confidence sequence for the running average \(\bar\delta^{v,c}_t := \frac{1}{t-s^v}\sum_{u=s^v+1}^t \delta_u\), that is, \[\mathbb{P}\!\left( \forall t\ge s^v + 1:\; L_t \le \bar\delta^{v,c}_t \le U_t \right) \ge 1-\alpha.\] Then the stopping time \[\tau_{\mathrm{w}}^{v,c} := \inf\!\left\{ t\ge s^v + 1:\; L_t > 0 \right\}\] defines an anytime-valid test of the weak null hypothesis, with guarantees analogous to those of the betting-based test for the strong null.

In practice, we use the empirical Bernstein CS [15], which has recently been successfully applied to online model comparison [28] and sequential forecasters evaluation [26].

Algorithmic details are given in Algorithm 1. Details on UP approximation, the empirical Bernstein CS, the \({\alpha_{v,c}}\) schedule, and challenger generation are given in Appendix 8.

4 Theoretical Guarantees↩︎

We establish guarantees for the proposed sequential split-selection mechanism under two notions of improvement: a strong (anytime advantage) hypothesis \(H_0^{v,c}\) and a weak (average advantage) hypothesis \(H_{\mathrm{w},0}^{v,c}\). These correspond respectively to testing-by-betting and confidence-sequence–based tests. Proofs and technical details are deferred to the appendix.

4.1 Anytime Validity and Global Error Control↩︎

Both tests are anytime-valid: they control Type I error under arbitrary, data-dependent stopping times and without independence assumptions.

4.2 Power: Finite Commitment Under Advantage↩︎

When a candidate split enjoys a persistent predictive advantage, both tests commit in finite time.

4.3 Guarantees Under Stationary Data↩︎

Under stationary data, the proposed procedure enjoys a stronger guarantee: the expected predictive performance of the deployed tree improves monotonically over time.

4.4 Warm-up experiment↩︎

We evaluate the practical implications of our stationarity guarantees on a controlled synthetic benchmark. Data are generated i.i.d.from a fixed, tree-structured distribution using the RandomTree generator introduced in the original Hoeffding Tree work [8]. This generator constructs a random decision tree by recursively splitting features at random and assigning class labels at the leaves. We use \(10\) numerical and \(10\) categorical features and generate trees of depth \(4\), corresponding to at most \(8\) leaves.

We compare the HT with our Anytime-Valid Tree (AVT) based on betting tests (\(\mathrm{AVT}_{\mathrm{B}}\)) and confidence sequences (\(\mathrm{AVT}_{\mathrm{CS}}\)). Unless stated otherwise, we use the same default hyperparameters across all experiments, namely \(n_{\min}=20\) and \(\varepsilon=0\). At each time step, generalisation performance is estimated using a fixed, independent holdout set of size \(200{,}000\) drawn from the same distribution.

4.4.0.1 Results.

Figure 2 highlights a clear contrast between methods. The HT exhibits multiple abrupt drops in generalisation performance. Notably, this behaviour occurs despite the data being fully i.i.d.and stationary.

In contrast, both anytime-valid variants avoid such collapses and display stable, monotone improvement in generalisation, consistent with Theorem 5. The HT also commits substantially more splits than our methods, leading to larger and less stable trees. Our approach caps the number of leaves at \(8\), matching the size of the ground-truth tree.

Regarding the two anytime-valid methods, we observe that the variant based on the weak (average-based) hypothesis performs slightly worse in practice. This variant commits to splits later than the strong-hypothesis test, which translates into delayed adaptation and inferior predictive performance.

Finally, the HT’s slight performance advantage at very large sample sizes is expected: By committing to many splits, it reduces approximation bias irrespective of split quality, and as estimation variance vanishes with more data, the model can perform well asymptotically.

2pt

5 Experiments↩︎

We evaluate our approach against (i) the Hoeffding Tree (HT) and (ii) its ensemble counterpart, Adaptive Random Forests (ARF). In both cases, we replace the HT base learner with our proposed Anytime-Valid Tree (AVT), yielding an Anytime-Valid Forest (AVF). In the main paper, we report results only for the betting-based variant (\(\mathrm{AVT}_{\mathrm{B}}\)), as it performs better overall than the CS version (\(\mathrm{AVT}_{\mathrm{CS}}\)), whose results are deferred to the Appendix 9.1. Nevertheless, any positive advantage observed for \(\mathrm{AVT}_{\mathrm{B}}\) over the baselines also carries over to \(\mathrm{AVT}_{\mathrm{CS}}\). While our primary focus is improving HT and ARF, additional streaming baselines are reported in Appendix 9.2. All methods are implemented using the river framework [30].

We evaluate all methods on 12 data streams, comprising six regression and six classification tasks.

Regression tasks: bike, predicting daily bike-sharing usage; chick, modeling poultry growth trajectories; fried, forecasting food consumption patterns; nzenergy, forecasting regional energy consumption; house, predicting house prices; and abalone, estimating abalone age from physical measurements.

Classification tasks: elec2, predicting electricity price movements (up/down); airlines, predicting flight delays; http-KDD99, detecting HTTP network intrusions; creditcard, detecting fraudulent transactions; rbfm100k, a synthetic stream with gradual drift; and hyper100k, a synthetic stream with linear drift.

For regression tasks, we enforce bounded losses via an adaptive scaling procedure. At each time step, we maintain an online estimate of the maximal observed loss and rescale the current loss, clipping it to \([0,1]\). For both regression and classification, we use the squared loss \(\ell(p,y)=\lVert p-y\rVert^2\).

5.0.0.1 Evaluation protocol.

Evaluation is conducted using the standard prequential (test-then-train) protocol. We report classification accuracy and regression MAE, visualized in two ways: the left panels show the prequential performance curves averaged over \(10\) independent runs (with shaded \(95\%\) confidence intervals), together with the evolution of tree depth over time; for ensemble methods, we report the average tree depth across trees to enable direct comparison with single-tree models; and the right panels display the distribution of aggregate performance across runs.

5.0.0.2 Model Performance and Complexity.

Figure 3 summarizes these results. Across the \(12\) data streams, our anytime-valid tree (\(\mathrm{AVT}_{\mathrm{B}}\)) outperforms the standard HT on the majority of datasets, with abalone being the main exception where HT attains better aggregate performance. On several streams, including bike, fried, and hyper100k \(\mathrm{AVT}_{\mathrm{B}}\) is competitive with and occasionally surpasses the ensemble baseline ARF. Importantly, gains persist throughout the stream, as reflected by the prequential curves.

Among all approaches, \(\mathrm{AVF}_{\mathrm{B}}\) achieves the strongest overall performance across nearly all datasets, consistently outperforming the standard ARF baseline. Overall, performance differences become more pronounced on datasets exhibiting consistent drops or increased volatility over time, where betting-based methods adapt more effectively.

In terms of model complexity, \(\mathrm{AVF}_{\mathrm{B}}\) in addition of providing the best model also produces the smallest trees on average, even compared to single-tree methods. By contrast, \(\mathrm{AVT}_{\mathrm{B}}\) tends to grow deeper trees compared to its baseline HT. This is expected: in the absence of ensembling, a single tree must capture greater heterogeneity in the data stream, requiring additional depth to match the accuracy achievable by an ensemble.

5.0.0.3 Computational Cost.

Table 1 reports per-instance inference and update times (mean \(\pm\) std over \(10\) runs). Inference costs for \(\mathrm{AVT}_{\mathrm{B}}\) remain comparable to HT, since prediction involves only standard tree traversal. The primary computational overhead arises during updates, where betting wealth is maintained for each candidate split.

As expected, betting-based methods incur higher update costs due to (i) maintaining shadow challenger statistics, and (ii) estimating the Universal Portfolio wealth.

Despite this additional cost, runtimes remain within practical bounds. For most datasets, update times stay within a few milliseconds per instance. Even on more demanding streams (e.g., nzenergy), costs remain compatible with real-time processing.

Two factors further mitigate this overhead. First, \(\mathrm{AVF}_{\mathrm{B}}\) typically learns shallower trees, reducing the number of nodes requiring update; for example, it is even faster than its single-tree counterpart \(\mathrm{AVT}_{\mathrm{B}}\) on nzenergy. Second, computations across candidate splits and ensemble members are independent, making the method naturally amenable to parallelization. Overall, the results demonstrate a favorable computational trade-off for the observed performance gains.

6 Conclusion↩︎

We introduced an anytime-valid framework for split selection in online decision trees. Our approach corrects a fundamental limitation of existing methods based on fixed-sample concentration bounds by providing statistical guarantees that remain valid under data-dependent stopping rules, including non-stationary and dependent data streams. The resulting procedure serves as a drop-in replacement for standard Hoeffding Trees and integrates seamlessly into ensemble methods such as Adaptive Random Forests, a state-of-the-art bagging-based approach for data stream learning. Empirical evaluations on a diverse suite of real-world streaming datasets demonstrate that the resulting ensembles consistently outperform existing baselines while producing substantially smaller trees.

Disclaimer↩︎

This paper was prepared for informational purposes by the Artificial Intelligence Research group of JPMorgan Chase & Co., and its affiliates (“JP Morgan”) and is not a product of the Research Department of JP Morgan. JP Morgan makes no representation, and warranty whatsoever, and disclaims all liability, for the completeness, accuracy or reliability of the information contained herein. This document is not intended as investment research or investment advice, or a recommendation, offer or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction, and shall not constitute a solicitation under any jurisdiction or to any person, if such solicitation under such jurisdiction or to such person would be unlawful.

© 2026 JP Morgan Chase & Co. All rights reserved.

Impact Statement↩︎

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

[31]

7 Proofs↩︎

7.1 Basic measurability and boundedness↩︎

Fix a node–candidate pair \((v,c)\) and a test start time \(s:=s^{v,c}\). By construction, the incumbent and challenger predictions at time \(t\) depend only on data observed up to time \(t-1\) and any algorithmic randomness revealed by then; thus they are \(\mathcal{F}_{t-1}\)-measurable. Since the loss \(\ell\) is deterministic given a prediction and \(Y_t\), the difference \(\Delta_t^{v,c}=\ell(m^v_{t-1},Y_t)-\ell(m^{v_c}_{t-1},Y_t)\) is \(\mathcal{F}_t\)-measurable.

Assume \(\Delta_t^{v,c}\in[-1,1]\) a.s. and a predictable betting fraction \(\beta_t^{v,c}\in[0,1]\), i.e.\(\beta_t^{v,c}\) is \(\mathcal{F}_{t-1}\)-measurable. Then the multiplicative factor satisfies \(1+\beta_t^{v,c}\Delta_t^{v,c}\in[0,2]\) a.s., hence the wealth \[W_{s-1}^{v,c}=1,\qquad W_t^{v,c}=W_{t-1}^{v,c}\bigl(1+\beta_t^{v,c}\Delta_t^{v,c}\bigr),\;t\ge s,\] is well-defined and nonnegative.

7.2 Proof of Lemma 1↩︎

Under the null hypothesis \(H_0^{v,c}\) we have \(\mathbb{E}[\Delta_t^{v,c}\mid\mathcal{F}_{t-1}]\le 0\) for all \(t\ge s\). Using predictability of \(\beta_t^{v,c}\) and \(\mathcal{F}_{t-1}\)-measurability of \(W_{t-1}^{v,c}\), \[\begin{align} \mathbb{E}[W_t^{v,c}\mid \mathcal{F}_{t-1}] &= \mathbb{E}\!\left[W_{t-1}^{v,c}\bigl(1+\beta_t^{v,c}\Delta_t^{v,c}\bigr)\,\Big|\,\mathcal{F}_{t-1}\right]\\ &= W_{t-1}^{v,c}\Bigl(1+\beta_t^{v,c}\mathbb{E}[\Delta_t^{v,c}\mid\mathcal{F}_{t-1}]\Bigr) \;\le\; W_{t-1}^{v,c}. \end{align}\] Thus \((W_t^{v,c})_{t\ge s-1}\) is a nonnegative \(\mathcal{F}_t\)-supermartingale.

We now invoke Ville’s inequality: if \((W_t)_{t\ge 0}\) is a nonnegative supermartingale with \(W_0=1\), then for any \(a>0\), \(\mathbb{P}(\sup_{t\ge 0} W_t \ge a)\le 1/a\). Applying this with \(a=1/\alpha^{v,c}\) yields \[\mathbb{P}_{H_0^{v,c}}\!\left(\sup_{t\ge s} W_t^{v,c}\ge \frac{1}{\alpha^{v,c}}\right) \le \alpha^{v,c}.\] Finally, \(\{\tau^{v,c}<\infty\}\subseteq \{\sup_{t\ge s}W_t^{v,c}\ge 1/\alpha^{v,c}\}\), so \(\mathbb{P}_{H_0^{v,c}}(\tau^{v,c}<\infty)\le \alpha^{v,c}\) as claimed.

We can prove similarly the same result for the weak hypothesis \(H_{\mathrm w,0}^{v,c}\). 0◻

7.3 Countability under adaptive tree growth↩︎

We record a simple sufficient condition for countability, used by Theorem 8. Suppose (i) at each time \(t\) the algorithm maintains finitely many current nodes, and (ii) each node \(v\) has a finite candidate class \(C_v\). Then the set of all tests ever instantiated up to any finite time \(t\) is finite; hence the set of tests over all times \(t\in\mathbb{N}\) is a countable union of finite sets and therefore countable.

7.4 Proof of Theorem 8↩︎

Let \(\mathcal{T}\) denote the (a.s.countable) set of all tests instantiated by the algorithm, indexed by pairs \((v,c)\). For each test define the “false rejection” event \[E^{v,c}:=\{H_0^{v,c}\;\text{holds and}\;\tau^{v,c}<\infty\}.\] By Lemma 1, \(\mathbb{P}(E^{v,c})\le \alpha^{v,c}\) for each \((v,c)\in\mathcal{T}\), regardless of dependence across tests. Hence by the union bound over the countable family, \[\mathbb{P}\!\left(\bigcup_{(v,c)\in\mathcal{T}} E^{v,c}\right) \;\le\; \sum_{(v,c)\in\mathcal{T}} \mathbb{P}(E^{v,c}) \;\le\; \sum_{(v,c)\in\mathcal{T}} \alpha^{v,c} \;\le\; \alpha.\] This proves the stated global control. 0◻

7.5 Proof of Theorem 5↩︎

We prove monotone expected performance of the deployed predictor \((\hat{m}_t)_{t\ge 0}\) produced by the procedure under i.i.d.data and convex losses, on the event \(\mathcal{E}\) that no false split is ever committed. For clarity, we focus on the classification setting; however, the result extends directly to any bounded-output prediction problem. Recall the theorem says:

7.5.0.1 Standing notation.

Let \((\mathcal{F}_t)_{t\ge 0}\) be the natural filtration generated by the stream and the internal randomness of the algorithm. At each time \(t\ge 0\), \(\hat{m}_t\) denotes the deployed tree predictor after processing \(t\) samples; hence \(\hat{m}_t\) is \(\mathcal{F}_t\)-measurable. Let \((X,Y)\sim P\) be an independent fresh draw, independent of \(\mathcal{F}_t\). Define the (conditional) one-step-ahead risk \[R_t \;:=\; \mathbb{E}\!\left[\ell(\hat{m}_t(X),Y)\,\middle|\,\mathcal{F}_t\right], \qquad \bar R_t \;:=\; \mathbb{E}\!\left[\ell(\hat{m}_t(X),Y)\,\middle|\,\mathcal{E}\right].\] Note that \(R_t\) is a random variable (measurable w.r.t.\(\mathcal{F}_t\)), while \(\bar R_t\) is a deterministic scalar.

We decompose each update \(t\mapsto t+1\) into two parts: (i) a parameter update of the leaf statistics (empirical probabilities), and (ii) possibly a structural update (a committed split). We show that each part is non-increasing in expected risk on \(\mathcal{E}\), which implies the claimed monotonicity.

7.5.1 Step 1: Marshall–Proschan implies monotone plug-in risk↩︎

The next lemma is the key tool controlling the fact that for convex losses, the expected risk of an empirical-mean predictor is nonincreasing with sample size.

7.5.2 Step 2: Parameter updates (no split) cannot increase expected risk↩︎

We now lift Lemma 3 from a single Bernoulli mean to the full tree. When no split is committed, each new observation updates the statistics of exactly one leaf, and convexity ensures that this update cannot increase the expected risk.

7.5.3 Step 3: Structural updates (committed splits) reduce expected risk on \(\mathcal{E}\)↩︎

We now handle the remaining case: the algorithm commits a split at time \(t\). Although the theorem statement does not explicitly mention incumbents and challengers, the commit rule is defined via an anytime-valid test comparing the prequential performance of the currently deployed leaf predictor to that of its challenger split. We use this comparison only inside the proof to show that the commit step is risk-improving on \(\mathcal{E}\).

7.5.3.1 Prequential comparison and instantaneous advantage.

Fix a candidate split \((v,c)\) that is defined at time \(t\) (i.e., its incumbent leaf \(v\) exists in the deployed tree at time \(t-1\) and the challenger children \(v_c^L,v_c^R\) are well-defined). Both incumbent and challenger predictors are prequential and \(\mathcal{F}_{t-1}\)-measurable: \[m^{v}_{t-1}(x)=p_{t-1}(v), \qquad m^{v_c}_{t-1}(x)= \begin{cases} p_{t-1}(v_c^L), & x\in R(v_c^L),\\[1mm] p_{t-1}(v_c^R), & x\in R(v_c^R). \end{cases}\] After observing \((X_t,Y_t)\), define the bounded prequential loss difference \[\Delta_t^{v,c} := \ell\!\left(m^v_{t-1}(X_t),Y_t\right) - \ell\!\left(m^{v_c}_{t-1}(X_t),Y_t\right) \in[-1,1], \qquad \delta_t^{v,c}:=\mathbb{E}\!\left[\Delta_t^{v,c}\mid \mathcal{F}_{t-1}\right].\]

7.5.3.2 Prequential mean equals fresh-draw mean.

Let \((X,Y)\sim P\) be an independent fresh draw, independent of \(\mathcal{F}_{t-1}\). The next lemma allows us to interpret \(\delta_t^{v,c}\) as the conditional fresh-draw risk gap between the incumbent and challenger, which is the quantity needed to argue that committing the split improves risk.

Applying Lemma 5 with \(g(x,y)=\ell(m^v_{t-1}(x),y)-\ell(m^{v_c}_{t-1}(x),y)\) yields the identity \[\delta_t^{v,c} = \mathbb{E}\!\left[ \ell(m^v_{t-1}(X),Y)-\ell(m^{v_c}_{t-1}(X),Y) \,\middle|\,\mathcal{F}_{t-1} \right],\] i.e., \(\delta_t^{v,c}\) is the conditional fresh-draw advantage of the challenger we use in the next sections, with \(\Delta_t^{v,c} = \ell(m^v_{t-1}(X),Y)-\ell(m^{v_c}_{t-1}(X),Y)\)

7.5.3.3 A bounded-drift correction for the weak (average-advantage) test.

The weak test controls a running average of the advantage process \(\delta_t^{v,c}\), whereas committing a split requires a guarantee on the instantaneous advantage at the commit time. We bridge this gap by showing that, between committed splits, the process \(t\mapsto\delta_t^{v,c}\) admits a uniformly bounded one-step drift. This allows us to introduce a correction threshold \(\epsilon\) such that a positive average advantage implies a positive instantaneous advantage at the commit time.

We present two ways of selecting \(\epsilon\): a conservative worst-case bound and a fully adaptive, data-dependent alternative. We emphasize that this threshold is introduced solely for theoretical control. In practice, the effective drift is often much smaller, and empirical results suggest that the required correction can be negligible and in some cases even set to zero while still preserving monotonicity.

7.5.3.4 From average advantage to instantaneous advantage.

Fix a candidate \((v,c)\) and suppose it is compared over a time interval during which no structural update affecting the relevant routing occurs. Let \[\bar\Delta_t^{v,c} :=\frac{1}{t-s^{v,c}} \sum_{r=s^{v,c}+1}^{t}\Delta_r^{v,c}, \qquad \bar\delta_t^{v,c} :=\frac{1}{t-s^{v,c}} \sum_{r=s^{v,c}+1}^{t}\delta_r^{v,c}.\] The next lemma converts a lower bound on the running average into a lower bound on the final instantaneous advantage.

7.5.3.5 Corrected weak-test stopping rule.

Let \((L_t,U_t)\) be a confidence sequence for the running average \(\bar\delta_t^{v,c}\), so that on its coverage event \(L_t\le\bar\delta_t^{v,c}\) for all \(t\ge s^{v,c}+1\). Combining Lemmas 6–7, on the coverage event we have \[\delta_t^{v,c} \ge L_t-\frac{\rho(t-s^{v,c}-1)}{2}.\] Therefore, to ensure an instantaneous margin \(\varepsilon\ge0\) at the commit time, one may use the corrected weak-test stopping time \[\tau_{\mathrm{w,bd}}^{v,c} := \inf\left\{ t\ge s^{v,c}+1: L_t>\varepsilon+\frac{\rho(t-s^{v,c}-1)}{2} \right\}, \qquad \rho:=\frac{4}{n_{\min}+1}.\]

7.5.4 Adaptive bounded-drift correction using leaf counts↩︎

The minimum leaf sample size requirement in Assumption 1 can be removed by controlling the one-step variation of the instantaneous prequential advantage using the actual leaf counts involved in the shadow incumbent and shadow challenger predictions.

7.5.4.1 Adaptive weak-test stopping rule.

Combining Lemmas 8 and 9, on the CS coverage event it is enough to use \[\tau_{\mathrm{w,ad}}^{v,c} := \inf\left\{ t\ge s^{v,c}+1: L_t> \varepsilon+ \frac{1}{t-s^{v,c}} \sum_{j=1}^{t-s^{v,c}-1} j\,\rho_{s^{v,c}+j} \right\},\] where \[\rho_u := \frac{2}{n^{\mathrm{inc}}_u+1} + \frac{2}{n^{\mathrm{chal}}_u+1}.\] This corrects the adaptive average-to-last penalty: the appropriate drift budget is the weighted sum \((t-s^{v,c})^{-1}\sum_j j\rho_{s^{v,c}+j}\), not the unweighted one-half sum.

7.5.4.2 Stationary risk certificate as a direct alternative.

The weak-test corrections above are one route to certifying instantaneous commit-time advantage. Under stationarity, a cleaner alternative is to certify the current risk improvement directly.

7.5.4.3 Commit is risk-improving on \(\mathcal{E}\).

We now isolate the structural effect of committing a split. Let \(\hat{m}_t^{sp}\) be the intermediate deployed predictor obtained before the leaf-statistics update at time \(t\) but after committing the split, and let \(\hat{m}_t\) be the deployed predictor after committing the split.

7.5.5 Step 4: Conclude the theorem↩︎

7.6 Proof of Theorem 4↩︎

We prove the two commitment guarantees in Theorem 4:

1. Under the strong alternative, the betting/wealth stopping time \(\tau^{v,c}\) is finite, and admits a high-probability bound of order \(\tilde{\mathcal{O}}(\log(1/\alpha^{v,c})/\Delta^2)\).

2. Under the weak alternative, the CS-crossing stopping time \(\tau_{\mathrm{w}}^{v,c}:=\inf\{t\ge s^{v,c}:L_t>0\}\) is finite with probability at least \(1-\alpha^{v,c}\), and admits the same rate when instantiated with the (empirical Bernstein) confidence sequence [26] used.

7.6.0.1 Global notation.

Fix a node–candidate pair \((v,c)\) and suppress superscripts \((v,c)\). Let the test start time be \(s:=s^{v,c}\). For brevity write \[\Delta_t:=\Delta_t^{v,c}\in[-1,1], \qquad \delta_t:=\mathbb{E}[\Delta_t\mid\mathcal{F}_{t-1}], \qquad t\ge s.\] We also set \(n:=t-s+1\) for the effective sample size at time \(t\ge s\).

The wealth of the betting-based test defined in (3 ) using the betting fraction (4 ) can be expressed as a continuous mixture over betting fractions, \[\label{eq:UP95continuous95app} W_t = \int_0^1 \prod_{i=s}^{t} \bigl(1+\beta\,\Delta_i\bigr) \,d\pi(\beta),\tag{5}\] where \(\pi\) denotes the Jeffreys prior on \([0,1]\).

In practice, we have to resort to approximation. We use a finite discrete mixture that allows to maintain the theoretical guarantees.

7.6.1 Part I: Wealth (betting) stopping time under the strong alternative↩︎

We first prove the wealth-based guarantee for the actual discrete-mixture wealth used by the algorithm.

7.6.1.1 Original discrete-mixture wealth and stopping rule.

Let \(\mathcal{B}=\{\beta_1,\ldots,\beta_K\}\subset[0,1)\) be the fixed grid of betting fractions and let \(w_k>0\) with \(\sum_{k=1}^K w_k=1\). The wealth is \[\label{eq:discrete95wealth95power} W_t = \sum_{k=1}^K w_k \prod_{u=s}^{t} \bigl(1+\beta_k\Delta_u\bigr), \qquad W_{s-1}=1.\tag{6}\] The betting stopping time is \[\tau:=\tau^{v,c} := \inf\left\{t\ge s: W_t\ge \frac{1}{\alpha^{v,c}} \right\}.\]

7.6.1.2 Goal.

We show that for every \(\eta\in(0,1)\), with probability at least \(1-\eta\), \[\tau \le t_0+N_\eta-1,\] where \[\label{eq:N95eta95discrete95power} N_\eta := \left\lceil \frac{32}{\Delta^2} \left( \log\frac{1}{\alpha^{v,c}} + \log\frac{1}{w_\star} + B_0 + \log\frac{1}{\eta} \right) \right\rceil, \qquad B_0:=n_0\log\frac{1}{1-\beta_\star}.\tag{7}\]

Step 0: Lower-bound the original mixture by one favorable grid point↩︎

For every \(t\ge s\), the mixture contains the component indexed by \(\beta_\star\), so deterministically \[\label{eq:mixture95lower95one95component} W_t \ge w_\star \prod_{u=s}^{t} \bigl(1+\beta_\star\Delta_u\bigr).\tag{8}\] Because \(\Delta_u\in[-1,1]\) and \(\beta_\star<1\), each factor is strictly positive: \[1+\beta_\star\Delta_u \ge 1-\beta_\star > 0.\] Thus we may take logarithms. At time \(t=t_0+N-1\), split the log-product into the pre-advantage block \(u=s,\ldots,t_0-1\) and the post-advantage block \(u=t_0,\ldots,t_0+N-1\): \[\begin{align} \log W_{t_0+N-1} &\ge \log w_\star + \sum_{u=s}^{t_0-1}\log(1+\beta_\star\Delta_u) + \sum_{u=t_0}^{t_0+N-1}\log(1+\beta_\star\Delta_u). \label{eq:logW95split95pre95post} \end{align}\tag{9}\]

Step 1: Control the stale pre-advantage history↩︎

No sign or mean condition is imposed before \(t_0\). Nevertheless, boundedness alone gives a deterministic lower bound. Since \(\Delta_u\ge -1\), \[1+\beta_\star\Delta_u \ge 1-\beta_\star,\] and hence \[\log(1+\beta_\star\Delta_u) \ge \log(1-\beta_\star) = -\log\frac{1}{1-\beta_\star}.\] There are \(n_0=t_0-s\) pre-advantage tested increments, so \[\label{eq:stale95history95bound} \sum_{u=s}^{t_0-1}\log(1+\beta_\star\Delta_u) \ge -n_0\log\frac{1}{1-\beta_\star} = -B_0.\tag{10}\] This is the only cost of using the original single-start wealth rather than a restart mixture. We could, in fact, circumvent this cost entirely by utilizing the restart mixture defined below:

For late-emerging advantages, one may allocate capital across restart times. For deterministic weights \(\pi_r\ge0\), \(\sum_{r=s}^{\infty}\pi_r\le1\), define \[\widetilde{W}_t = \sum_{r=s}^{t}\pi_r \sum_{k=1}^K w_k\prod_{u=r}^{t}(1+\beta_k\Delta_u) + \sum_{r>t}\pi_r.\] Each started component is an e-process under the strong null, and unstarted capital is held in cash, so \((\widetilde{W}_t)\) is a nonnegative supermartingale. If the advantage starts at \(t_0\), the component \(r=t_0\) pays a penalty \(\log(1/\pi_{t_0})\) instead of the stale-history term. This is a valid optional variant but is a different algorithmic wealth process.

Step 2: Concentration of the post-advantage cumulative loss difference↩︎

Fix a block length \(N\ge1\) and define, for \(u\ge t_0\), \[X_u:=\Delta_u-\delta_u.\] Then \((X_u,\mathcal{F}_u)\) is a martingale difference sequence: \[\mathbb{E}[X_u\mid\mathcal{F}_{u-1}] = \mathbb{E}[\Delta_u-\delta_u\mid\mathcal{F}_{u-1}] = \delta_u-\delta_u =0.\] Moreover, since \(\Delta_u\in[-1,1]\), its conditional mean \(\delta_u\) also lies in \([-1,1]\), and \(X_u\) lies conditionally in an interval of length at most \(2\). By the conditional Hoeffding lemma, for every \(\lambda>0\), \[\mathbb{E}\!\left[\exp(-\lambda X_u)\mid\mathcal{F}_{u-1}\right] \le \exp\left(\frac{\lambda^2}{2}\right).\] Iterating this inequality over \(u=t_0,\ldots,t_0+N-1\) gives \[\mathbb{E}\!\left[ \exp\left(-\lambda\sum_{u=t_0}^{t_0+N-1}X_u\right) \right] \le \exp\left(\frac{N\lambda^2}{2}\right).\] Therefore, by Chernoff’s method, for any \(a>0\), \[\mathbb{P}\!\left( \sum_{u=t_0}^{t_0+N-1}X_u\le -a \right) \le \exp\left(-\frac{a^2}{2N}\right).\] Taking \(a=\sqrt{2N\log(1/\eta)}\), we obtain an event \(\mathcal{A}_N\) satisfying \(\mathbb{P}(\mathcal{A}_N)\ge1-\eta\) on which \[\label{eq:mart95diff95lower95discrete} \sum_{u=t_0}^{t_0+N-1}X_u \ge -\sqrt{2N\log\frac{1}{\eta}}.\tag{11}\] On \(\mathcal{A}_N\), using \(\delta_u\ge\Delta\) for \(u\ge t_0\), \[\begin{align} \sum_{u=t_0}^{t_0+N-1}\Delta_u &= \sum_{u=t_0}^{t_0+N-1}\delta_u + \sum_{u=t_0}^{t_0+N-1}X_u \nonumber\\ &\ge N\Delta - \sqrt{2N\log\frac{1}{\eta}}. \label{eq:cum95delta95lower95discrete} \end{align}\tag{12}\] If \[\label{eq:N95concentration95requirement95discrete} N\ge \frac{8}{\Delta^2}\log\frac{1}{\eta},\tag{13}\] then \[\sqrt{2N\log\frac{1}{\eta}}\le \frac{N\Delta}{2},\] and therefore on \(\mathcal{A}_N\), \[\label{eq:cum95delta95half95discrete} \sum_{u=t_0}^{t_0+N-1}\Delta_u \ge \frac{N\Delta}{2}.\tag{14}\]

Step 3: Convert cumulative advantage into log-wealth growth↩︎

We use the elementary inequality \[\log(1+x)\ge x-x^2, \qquad x\in[-1/2,1/2].\] Indeed, for \(g(x)=\log(1+x)-x+x^2\), one has \(g(0)=0\) and \(g'(x)=x(1+2x)/(1+x)\), so \(g\) is minimized at zero on \([-1/2,1/2]\). Since \(\beta_\star\le\Delta/4\le1/4\) and \(\Delta_u\in[-1,1]\), the product \(x=\beta_\star\Delta_u\) lies in \([-1/4,1/4]\). Hence \[\log(1+\beta_\star\Delta_u) \ge \beta_\star\Delta_u- \beta_\star^2\Delta_u^2 \ge \beta_\star\Delta_u- \beta_\star^2.\] Summing over the post-advantage block and using 14 , on \(\mathcal{A}_N\) we get \[\begin{align} \sum_{u=t_0}^{t_0+N-1}\log(1+\beta_\star\Delta_u) &\ge \beta_\star \sum_{u=t_0}^{t_0+N-1}\Delta_u - N\beta_\star^2 \nonumber\\ &\ge N\left(\frac{\beta_\star\Delta}{2}-\beta_\star^2\right). \label{eq:post95log95growth95first} \end{align}\tag{15}\] Because \(\beta_\star\le\Delta/4\), \[\beta_\star^2\le \frac{\beta_\star\Delta}{4},\] so \[\frac{\beta_\star\Delta}{2}-\beta_\star^2 \ge \frac{\beta_\star\Delta}{4}.\] Because \(\beta_\star\ge\Delta/8\), \[\frac{\beta_\star\Delta}{4} \ge \frac{\Delta^2}{32}.\] Therefore, on \(\mathcal{A}_N\) and under 13 , \[\label{eq:post95log95growth95discrete} \sum_{u=t_0}^{t_0+N-1}\log(1+\beta_\star\Delta_u) \ge \frac{N\Delta^2}{32}.\tag{16}\]

Step 4: Solve for threshold crossing↩︎

Combining 9 , 10 , and 16 , on \(\mathcal{A}_N\) we have \[\label{eq:logW95final95discrete95lower} \log W_{t_0+N-1} \ge \log w_\star - B_0 + \frac{N\Delta^2}{32}.\tag{17}\] Thus \(W_{t_0+N-1}\ge1/\alpha^{v,c}\) is guaranteed whenever \[\log w_\star - B_0 + \frac{N\Delta^2}{32} \ge \log\frac{1}{\alpha^{v,c}},\] or equivalently whenever \[\label{eq:N95threshold95discrete} \frac{N\Delta^2}{32} \ge \log\frac{1}{\alpha^{v,c}} + \log\frac{1}{w_\star} + B_0.\tag{18}\] The choice \(N=N_\eta\) in 7 implies 18 . It also implies the concentration requirement 13 , because the bracket in 7 contains \(\log(1/\eta)\) and \(32\ge8\). Therefore, \[\mathbb{P}\!\left( W_{t_0+N_\eta-1}\ge\frac{1}{\alpha^{v,c}} \right) \ge 1-\eta.\] By definition of \(\tau\), \[\mathbb{P}\!\left( \tau\le t_0+N_\eta-1 \right) \ge 1-\eta.\]

7.6.1.3 Almost sure finiteness.

For every \(\eta\in(0,1)\), there is a deterministic finite \(N_\eta\) such that \[\mathbb{P}\!\left(\tau>t_0+N_\eta-1\right)\le\eta.\] Since \(\{\tau=\infty\}\subseteq\{\tau>t_0+N_\eta-1\}\), we have \(\mathbb{P}(\tau=\infty)\le\eta\) for every \(\eta\in(0,1)\). Letting \(\eta\downarrow0\) gives \(\mathbb{P}(\tau=\infty)=0\), so \(\tau<\infty\) almost surely.

7.6.1.4 Stale-history penalty.

Since \(\beta_\star\le\Delta/4\le1/4\), \[B_0=n_0\log\frac{1}{1-\beta_\star} \le \frac{n_0\beta_\star}{1-\beta_\star} \le \frac{4}{3}n_0\beta_\star \le \frac{n_0\Delta}{3}.\] Thus the original single-start wealth pays an explicit stale-history penalty. Validity holds for any finite grid; the rate above additionally requires that the grid contain a betting fraction of order \(\Delta\), namely \(\beta_\star\in[\Delta/8,\Delta/4]\).

7.6.2 Part II: CS-crossing stopping time under the weak alternative↩︎

We now prove the CS part under the weak alternative.

7.6.2.1 Running averages.

For \(t\ge s\) define \[\bar\Delta_t := \frac{1}{t-s+1}\sum_{u=s}^t \Delta_u, \qquad \bar\delta_t := \frac{1}{t-s+1}\sum_{u=s}^t \delta_u.\] The weak null and weak alternative are: \[H_{\mathrm{w},0}:\;\forall t\ge s,\;\bar\delta_t\le 0, \qquad H_{\mathrm{w},1}(\Delta):\;\exists t_0\ge s\;\text{s.t.}\;\forall t\ge t_0,\;\bar\delta_t\ge \Delta.\]

7.6.2.2 Confidence sequence and stopping rule.

Let \((L_t,U_t)_{t\ge s}\) be a \((1-\alpha^{v,c})\) CS for \(\bar\delta_t\): \[\label{eq:CS95cover95full} \mathbb{P}\Bigl(\forall t\ge s:\;L_t\le \bar\delta_t\le U_t\Bigr)\ge 1-\alpha^{v,c}.\tag{19}\] Define the CS-crossing stopping time \[\tau_{\mathrm{w}}:=\tau_{\mathrm{w}}^{v,c}:=\inf\{t\ge s:\;L_t>0\}.\]

Step 1: Generic crossing lemma↩︎

Using 19 , we immediately obtain: \[\mathbb{P}(\tau^{\mathrm{s}}<\infty)\ge \mathbb{P}(\mathcal{G})\ge 1-\alpha^{v,c}.\]

Step 2: Our explicit empirical Bernstein CS↩︎

We now directly define the empirical Bernstein CS used in our paper from [26], in the exact form needed for the proof.

7.6.2.3 Empirical Bernstein radius (time-uniform).

Assume \(\Delta_t\in[-1,1]\) a.s. Define the predictable empirical variance proxy \[\hat{V}_t := \frac{1}{t-s+1}\sum_{u=s}^{t} \bigl(\Delta_u-\bar\Delta_{u-1}\bigr)^2, \qquad \bar\Delta_{s-1}:=0.\] Let \[\ell_n(\alpha) := \log\frac{1}{\alpha}+\log\log\bigl(e n\bigr), \qquad n\ge 1,\] and define the (two-sided) empirical Bernstein half-width \[\label{eq:empbern95radius95full} r_n(\alpha) := \sqrt{\frac{2\hat{V}_t\,\ell_n(\alpha)}{n}} + \frac{3\,\ell_n(\alpha)}{n}, \qquad n=t-s+1.\tag{20}\] (Any equivalent time-uniform empirical Bernstein CS from our construction can be used here; constants are universal.)

Define \[L_t:=\bar\Delta_t-r_{t-s+1}(\alpha^{v,c}), \qquad U_t:=\bar\Delta_t+r_{t-s+1}(\alpha^{v,c}), \qquad t\ge s.\]

7.6.2.4 Width bound.

By construction, \[w_t = U_t-L_t = 2r_{t-s+1}(\alpha^{v,c}).\]

Step 3: Solving explicitly for the crossing time↩︎

By Lemma 12, on \(\mathcal{G}\) it suffices to have \[w_t<\Delta \quad\Longleftrightarrow\quad 2r_{n}(\alpha^{v,c})<\Delta, \qquad n=t-s+1.\] Using 20 , a sufficient condition is \[2\sqrt{\frac{2\hat{V}_t\,\ell_n(\alpha^{v,c})}{n}} + \frac{6\,\ell_n(\alpha^{v,c})}{n} <\Delta.\] Since \(\Delta_t\in[-1,1]\), we have the crude bound \(\hat{V}_t\le 4\) a.s., so a deterministic sufficient condition is \[\label{eq:det95suff95cond95cs} 2\sqrt{\frac{8\,\ell_n(\alpha^{v,c})}{n}} + \frac{6\,\ell_n(\alpha^{v,c})}{n} <\Delta.\tag{21}\] We now solve 21 .

7.6.2.5 Controlling the square-root term.

Require \[2\sqrt{\frac{8\,\ell_n}{n}} \le \frac{\Delta}{2} \quad\Longleftrightarrow\quad \sqrt{\frac{8\,\ell_n}{n}} \le \frac{\Delta}{4} \quad\Longleftrightarrow\quad \frac{8\,\ell_n}{n} \le \frac{\Delta^2}{16} \quad\Longleftrightarrow\quad n \ge \frac{128}{\Delta^2}\,\ell_n.\]

7.6.2.6 Controlling the linear term.

Also require \[\frac{6\,\ell_n}{n} \le \frac{\Delta}{2} \quad\Longleftrightarrow\quad n\ge \frac{12}{\Delta}\,\ell_n.\] Since \(\Delta\le 1\), the \(\Delta^{-2}\) requirement dominates asymptotically, so it is enough to enforce \[n\;\ge\;\frac{C}{\Delta^2}\,\ell_n(\alpha^{v,c})\] for a universal constant \(C\).

7.6.2.7 Self-consistency and the \(\log\log\) term.

Recall \(\ell_n(\alpha)=\log(1/\alpha)+\log\log(en)\). If we pick \[n \ge \frac{C}{\Delta^2}\left(\log\frac{1}{\alpha^{v,c}}+\log\log\frac{e}{\alpha^{v,c}}\right),\] then \(\log\log(en)\) is at most a constant times \(\log\log(e/\alpha^{v,c})\) (up to additive constants), so the inequality is self-consistent. Therefore, there exists a universal constant \(C'>0\) such that on \(\mathcal{G}\), \[\tau^{\mathrm{s}} \le t_0-1 + \frac{C'}{\Delta^2}\left(\log\frac{1}{\alpha^{v,c}}+\log\log\frac{e}{\alpha^{v,c}}\right),\] i.e., \[\tau^{\mathrm{s}}-t_0 = \tilde{\mathcal{O}}\!\left(\frac{\log(1/\alpha^{v,c})}{\Delta^2}\right) \quad\text{on }\mathcal{G}.\]

7.6.3 Final conclusion↩︎

8 Implementation Details and Parameters↩︎

This appendix provides implementation-specific details underlying Algorithm 1.

8.1 Discrete-Mixture Betting Strategy↩︎

In theory, the betting-based test can be expressed as a continuous mixture over betting fractions, \[\label{ghvolfei} W_t = \int_0^1 \prod_{i=s}^{t} \bigl(1+\beta\,\Delta_i\bigr) \,d\pi(\beta),\tag{22}\] where \(\pi\) denotes the Jeffreys prior on \([0,1]\). In practice, we have to resort to approximation. We use a finite discrete mixture, which eliminates approximation error entirely, and allow to maintain the theoretical guarantees

8.1.0.1 Discrete-mixture wealth.

Fix a finite grid of betting fractions \[\mathcal{B} := \{\beta_1,\dots,\beta_K\} \subset [0,1],\] for example a geometric or uniform grid such as \(\mathcal{B}=\{0,0.01,0.02,\dots,0.99\}\). Let \(\{w_k\}_{k=1}^K\) be nonnegative prior weights satisfying \(\sum_{k=1}^K w_k=1\).

The betting wealth is defined as \[\label{eq:UP95discrete95app} W_t := \sum_{k=1}^K w_k \prod_{i=s}^{t} \bigl(1+\beta_k\,\Delta_i\bigr).\tag{23}\] For each \(k\), the process \(W_t^{(k)}:=\prod_{i=s}^{t}(1+\beta_k\Delta_i)\) is a nonnegative supermartingale under the null hypothesis \(\mathbb{E}[\Delta_t\mid\mathcal{F}_{t-1}]\le 0\). Therefore, \(W_t\) is itself a nonnegative supermartingale.

8.1.0.2 Validity and efficiency.

This construction has three key consequences: (i) Exact anytime-validity: a finite sum of supermartingales remains a supermartingale, so Ville’s inequality applies directly; (ii) Approximation of the continuous Universal Portfolio: standard online portfolio results imply that a sufficiently fine grid approximates the continuous mixture up to an additive \(O(\log K)\) term in log-wealth; and (iii) computational efficiency: updating \(K\)grid points incurs only \(O(K)\) cost per step and is typically faster than Monte Carlo integration. We use \(K=100\).

Unless stated otherwise, all theoretical guarantees in the main text apply exactly to the discrete-mixture wealth 23 .

8.2 Significance-Level Allocation↩︎

We allocate significance levels only to tests that are actually instantiated. Let \(\mathcal{T}\) denote the random countable set of node–candidate tests ever created by the algorithm. It is enough for global validity that, pathwise, \[\sum_{(v,c)\in\mathcal{T}}\alpha^{v,c}\le \alpha .\]

One can use the following online alpha-spending rule. For \(d\ge0\), \(m\ge1\), and \(q\ge1\), define \[a_d=\frac{6}{\pi^2(d+1)^2},\qquad b_m=\frac{6}{\pi^2m^2},\qquad g_q=\frac{6}{\pi^2q^2}.\] Thus \(\sum_{d\ge0}a_d=\sum_{m\ge1}b_m=\sum_{q\ge1}g_q=1\).

For a node \(v\), let \(d(v)\) be its depth and let \(r(v)\) be its creation rank among nodes of the same depth. Candidate splits may be generated adaptively. Let \(q\) index the candidate-generation calls made at node \(v\). On the \(q\)-th call, after removing duplicate or previously tested candidates, suppose \(B_{v,q}\) new candidates remain. If \(B_{v,q}=0\), no level is spent. Otherwise, every new candidate \(c\) in that batch receives \[\boxed{ \alpha^{v,c} = \alpha_{\rm tree}\, a_{d(v)}\,b_{r(v)}\,g_q\, \frac{1}{B_{v,q}} } .\] For a single tree, take \(\alpha_{\rm tree}=\alpha\). For a forest with \(M\) trees, take \(\alpha_{\rm tree}=\alpha/M\).

The level \(\alpha^{v,c}\) is fixed before the first observation used to update the corresponding test statistic. Hence it is predictable at the test start time.

To verify summability, fix any realized run of the algorithm. Let \(\mathcal{V}\) be the set of nodes ever created and let \(\mathcal{C}_{v,q}\) be the set of new candidates instantiated at node \(v\) on proposal call \(q\). Then \[\begin{align} \sum_{(v,c)\in\mathcal{T}}\alpha^{v,c} &= \alpha_{\rm tree} \sum_{v\in\mathcal{V}} a_{d(v)}b_{r(v)} \sum_{q\ge1}g_q \sum_{c\in\mathcal{C}_{v,q}}\frac{1}{B_{v,q}} \\ &\le \alpha_{\rm tree} \sum_{d\ge0}a_d \sum_{m\ge1}b_m \sum_{q\ge1}g_q = \alpha_{\rm tree}. \end{align}\] Therefore \[\sum_{(v,c)\in\mathcal{T}}\alpha^{v,c}\le \alpha_{\rm tree}\] pathwise.

8.3 Candidate Split Generation↩︎

To avoid biasing the comparison, candidate splits are generated using exactly the same mechanisms as in the baseline Hoeffding Tree. Depending on the configuration, each node employs either a Gaussian splitter or a histogram-based splitter, maintaining feature-wise sufficient statistics. By default, HT uses the gaussien splitter. When queried, the node proposes a finite set of promising candidates based on empirical impurity reduction. In our experiments, we use the default setting of proposing up to 10 candidates per time step; however, we automatically discard duplicates and ensure that previously proposed splits are not re-evaluated.

Overall, we use exactly the same configuration as the default Hoeffding Tree. Our method only differs from the baseline only in the statistical test used to commit splits.

8.4 Empirical Bernstein Confidence Sequence↩︎

For the confidence-sequence–based test, we use a time-uniform empirical Bernstein confidence sequence as in [26]. Assume \(\Delta_t\in[-1,1]\) almost surely and let \(s\) denote the test start time.

8.4.0.1 Empirical Bernstein radius (time-uniform).

Define the running average \[\bar\Delta_t := \frac{1}{t-s+1}\sum_{u=s}^{t}\Delta_u, \qquad t\ge s,\] and the predictable empirical variance proxy \[\hat{V}_t := \frac{1}{t-s+1} \sum_{u=s}^{t} \bigl(\Delta_u-\bar\Delta_{u-1}\bigr)^2, \qquad \bar\Delta_{s-1}:=0.\]

Let \[\ell_n(\alpha) := \log\frac{1}{\alpha} + \log\log\!\bigl(e n\bigr), \qquad n\ge 1,\] and define the empirical Bernstein half-width \[\label{eq:empbern95radius95app} r_n(\alpha) := \sqrt{\frac{2\,\hat{V}_t\,\ell_n(\alpha)}{n}} + \frac{3\,\ell_n(\alpha)}{n}, \qquad n=t-s+1.\tag{24}\]

The resulting confidence sequence is \[L_t := \bar\Delta_t - r_{t-s+1}(\alpha^{v,c}), \qquad U_t := \bar\Delta_t + r_{t-s+1}(\alpha^{v,c}), \qquad t\ge s.\]

9 Additional experiments↩︎

This section presents supplementary experiments that further characterize the empirical behavior of our anytime-valid decision tree framework. We first isolate and compare the proposed betting-based and confidence-sequence–based split-certification mechanisms in Appendix 9.1, and then report additional comparisons against established streaming ensemble baselines in Appendix 9.2.

9.1 Comparison between \(\mathrm{AVT}_{\mathrm{B}}\) and \(\mathrm{AVT}_{\mathrm{CS}}\)↩︎

We compare \(\mathrm{AVT}_{\mathrm{B}}\) and \(\mathrm{AVT}_{\mathrm{CS}}\) across a diverse collection of real-world regression and classification data streams. The two methods differ only in the underlying anytime-valid testing mechanism used to certify splits betting-based tests for \(\mathrm{AVT}_{\mathrm{B}}\) versus confidence-sequence–based tests for \(\mathrm{AVT}_{\mathrm{CS}}\), allowing for a clean empirical comparison of their practical behavior. Figure 4 reports full prequential and distribution performance trajectories on twelve benchmark datasets.

Overall, \(\mathrm{AVT}_{\mathrm{CS}}\) underperforms \(\mathrm{AVT}_{\mathrm{B}}\), though it remains competitive with and typically outperforms—the ARF baseline.

9.2 Other baselines↩︎

In this section, we report additional comparisons against existing streaming ensemble baselines. We use the packages river [30] and CapyMOA [33] for the baselines. For classification, we use SOKNL [3], OnlineSmoothBoost [34], StreamingRandomPatches [2], OzaBoost [35], and ARF. For regression, we compare only against SOKNL and ARF, as the previous methods are not currently available for regression tasks.

As noted by [36], the streaming literature has predominantly focused on classification, with regression receiving comparatively limited attention until recently. We also exclude SGBT [37] from our evaluation due to unresolved implementation issues that prevent reliable use; details of the issues are provided in Appendix 10.

10 Implementation issues with baselines↩︎

During our evaluation, we encountered several implementation issues with existing baselines, most notably with the Streaming Gradient Boosting Tree (SGBT) [37].

10.0.0.1 Degenerate regression behavior.

When used for regression, SGBT consistently outputs a zero prediction throughout the entire stream, independently of the dataset or training progress. This behavior is illustrated by the diagnostic experiment shown in Fig. 6.

10.0.0.2 Source inspection.

Inspection of the source code reveals that the SGBT regressor inherits from a classifier-oriented base class (Fig. 7), which may implicitly enforce classification-specific behavior. We attempted several fixes but were unable to obtain a functioning regression variant.

10.0.0.3 Stability issues.

More broadly, several CapyMOA baselines exhibit recurrent runtime failures. For example, experiments on several datasets terminate with Java errors, which we were unable to resolve. All experiments were run on AWS EC2 instances. The main evaluation used a c7i.16xlarge instance (64 vCPUs, 128 GiB RAM), and we also attempted a memory-optimized r8a.16xlarge configuration (64 vCPUs, 512 GiB RAM), but the stability issues persisted.

11 Experiments details↩︎

All experiments were run on AWS EC2 instances. The main evaluation used a c7i.16xlarge instance (64 vCPUs, 128 GiB RAM).

References↩︎