Tree Ensembles for Contextual Bandits
Authors: Hannes Nilsson
Rikard Johansson
Niklas Åkerblom
Morteza Haghir Chehreghani
Venue: Accepted by TMLR ()

Abstract: We propose a new framework for contextual multi-armed bandits based on tree ensembles. Our framework adapts two widely used bandit methods, Upper Confidence Bound and Thompson Sampling, for both standard and combinatorial settings. As part of this framework, we propose a novel method of estimating the uncertainty in tree ensemble predictions. We further demonstrate the effectiveness of our framework via several experimental studies, employing XGBoost and random forests, two popular tree ensemble methods. Compared to state-of-the-art methods based on decision trees and neural networks, our methods exhibit superior performance in terms of both regret minimization and computational runtime, when applied to benchmark datasets and the real-world application of navigation over road networks.

Published in Transactions on Machine Learning Research (10/2024)
Tree Ensembles for Contextual Bandits
Hannes Nilsson]
kannesni@@chlnere..c
Chalmers University of Technology and University of Gothenburg
Rikard Johanssonf
rikjo
Chalmers University of Technology and University of Gothenburg
Niklas Akerblom
nilkas www..ckeeebooom@oooooooote
Volvo Car Corporation
Chalmers University of Technology and University of Gothenburg
Morteza Haghir Chehreghani
Chalmers University of Technology and University of Gothenburg
Reviewed on OpenReview: https: // openreview. net/ fermmf 5d=5900555
Abstract
We propose new framework for contextual multi-armed bandits based on ensem- bles. Our framework adapts two widely used bandit methods, Upper Confidence Bound and Thompson Sampling, for both standard and combinatorial settings. As part of this frame- work, we propose novel method of estimating the uncertainty in tree ensemble predictions. We further demonstrate the effectiveness of our framework via several experimental studies, employing XGBoost and random forests, two popular tree ensemble methods. Compared to state-of-the-art methods based on decision trees and neural networks, our methods ex- hibit superior performance terms of both regret minimization and computational runtime, when applied benchmark datasets and the real-world application of navigation over road networks.
1 Introduction
provide a principled framework for making optimal sequences of decisions under uncertainty. As discussed by Zhu & Van Roy (2023), MABs constitute a vital component modern recommendation systems for efficient exploration, among many other applications. An important variant known as the conteztual malli-arrmd bandit incorporates additional contextual side information into the decision-making process, allowing for more personalized or adaptive action selection. Following the recent success of (deep) neural networks in solving various machine learning tasks, several methods building such models have been suggested for finding functional relationships between the context and outcomes of actions to aid the decision- process (Zhou et al. 2020 Zhang et al. 2021 Zhu &
Stochastic multi-armed bandits (MABs) (see Slivkins 2019
Van Roy| 2023 Osband et al. 2021 Hoseini et al.) 2022). Even though sophisticated, these methods can be impractical, timo-consuming, and computationally expensive.
In light of these challenges, we propose bandit algorithms that utilize tree ensemble (TE) methods (Hastie et al. 2009), like pradient-boosted decision trees (GBDT) and random forests, comprehend the contextual features, combined with the most popular bandit methods Upper Confidence Bound (UCB) and Thompson Sampling (TS) as exploration strategies. Compared with other tree-based and neural network methods, our methods, called TEUCB and TETS, yield superior results on UCI benchmark datasets. Additionally, our methods benefit from more effective learning with less computational overhead on most problem instances, compared to existing methods that use similarly expressive machine learning models. We furthermore
*These authors contributed equally.

---

Published in Transactions on Machine Learning Research (10/2024)
extend the framework to the combinatorial contextual setting, a type of bandit that deals with complex combinatorial sets of arms, and investigate it on the important real-world application of efficient navigation in road networks. In this work, we focus on the practical applicability of the proposed framework in different settings and do not provide a theoretical analysis of the regret.
1.1 Related Work
The concept of applying decision trees to contextual bandit problems has been studied to limited extent. Elmachtoub et al. (2017) suggest using single decision tree for each arm available to the agent. Their method is referred to TreeBootstrup, the concept of bootstrapping is employed in order to resemble the Thompson Sampling process. One issue with their method is its limited ability to achieve the accuracy and robustness of tree ensemble methods, particularly when estimating complex reward functions. The possibility of applying random forests in their framework is discussed, but no concrete methods or experimental results are presented. Furthermore, storing and training one tree model per arm does not scale well, especially not with large action spaces (e.g., in the combinatorial setting), and could potentially lead to excessive exploration for dynamic arm sets, as it cannot attend to what it has learned from the contexts of other arms. In contrast. Féraud et al. (2016) employ tree ensemble but only use decision trees of unit depth, also known decision stumps. While tree ensembles with a large number of decision stumps tend to perform well regarding accuracy, lower variance, and incrcased robustness, restricting the depth in such an extreme way may not be adequate when addressing complex lasks (Hastie et al.) 2009). The experimental si udlee by Hastie et al. (2009) indicate that tree depths of 4 to 8 work well for boosting. Additionally, Féraud et al. (2016) only investigate the bandit algorithm known as successive elimination, which usually leads to less efficient exploration compared to UCB and TS, and thus is used less commonly. Moreover, the method, called Bandit Forest, requires binary encoded contextual features. Comparing these two tree-based bandit methods, Elmachtoub et al. (2017) experimentally show that TreeBootstrap tends to outperform Bandit Forest in practice. It should be noted that neither Elmachtoub et al. (2017) nor Féraud et al. (2016) consider combinatorial context ual bandits.
Apart from the two methods mentioned above, the problem has primarily been addressed using other ma- chine lcarning models. When the reward function is linear w.r.t. the context, LinUCB (Li et al.] 2010 Abbasi-Yadiae et al. 2011 and Lineor Thompson Sampling (LinTS) (Agrawal & Goyal 2013) have demon- strated good performance. In more complicated cases, the lincar assumption no longer holds, and thus more expressive models are needed.
In recent years, neural contextual bandits have attracted a lot of attention. As the name suggests, these methods use (deop) neural networks to model the expected rewards for some observed contextual features. Out of several proposed neural contextual bandit algorithms, NewralUCB (Zhou et al. 2020) and NearulTS (Zhang et al., 2021), in particular, have been shown to perform well, while also providing theoretical regret bounds. On the negative side, due to how these methods estimate the uncertainty in predictions, they rely inverting matrix of size equal to the number of network parameters, which is usually computationally expensive and time-consuming, especially when the prediction tasks require large neural networks.
Zhu & Van Roy 2023)) provide a thorough review of different neural bandit methods and suggest method based on epistemic neural networks (Osband et al.) 2021 for more efficient uncertainty modeling, showing its advantages terms of regret minimization and computational efficiency. Despite their promising results, we argue that neural networks may not necessarily be the most appropriate models for contextual bandits. For instance, even with epistemic neural networks, training is still resource-inlensive. On the other hand, there is large body of work that shows the effectiveness of tree ensemble methods for regression and classification tasks in the standard supervised learning setting [Borisov et al. 2022 Gorishniy et al.) 2021 Grinsztajn
et al. 2022), and therefore we believe that their extension to contextual bandits can have great potential.
One less directly related method is Ensemble Sampling (Lu & Van Roy 2017). where the ensembles are solely used for uncortainty estimation and not for modcling the reward functions bandits. Uncertainty estimates in Ensemble Sampling and similar methods focus on uncertainties in the parameters of the models used to approximate the underlying processes being sampled. Tn contrast, we sample directly from estimated
2

---

Published in Transactions on Machine Learning Research (10/2024)
distributions of the expected rewards given contexts. Our approach aligns closer with sampling- baasdd bandit methods like LinTS and NeuralTS.
2
Background
In this section, we describe the multi-armed bandit problem and its extensions relevant to our work.
2.1 Multi-Armed Bandit Problem
The multi-armed bandit (MAB) problem is a sequential decision decision-making problem under uncertainty, where the dccision maker, i.c., the agent, interactivcly learns from the environment over a horizon of time steps (interactions). At each time step S T, the agent is presented with a set of K actions A, commonly referred to as arms, Each action A has an (initially) unknown reward distribution with expected value Pa. The objective is to maximize the cumulative reward over the time horizon T, or more commonly (and equivalently) to minimize the cumulative regret, which is defined
T Σ (Ma--Mak - Mar),
R(T) &
(1)
where Pa- the expected reward of the optimal arm a", and a, is the arm selected at time step t. is important to note that the agent only receives leedback from the selected arm/action. More specifically, when selecting a the agent receives a reward fr,a, which is sampled from the underlying reward distribution. As previously mentioned, the agent's objective is to minimize the cumulative regret, not to learn the complete reward function for each arm. Thus, the agent has to balance delicately between exploration and exploitation.
2.2 Contextual Bandit Problem
The contextual multi-armed bandit problem is extension of the classical MAB problem described in Section 2.1 The agent is, at each time step i, presented with context vector Xt,a Rd for each action a E A. For example, a recommendation system could encode a combination of user-related and action- specific features into the context vector X4,a- Then, the expected reward action a at time t is given by an (unknown) function of the context g Rd >> IR, such that TE[r,,]] q(x,,)) Learning to generalize the relationship between the contextual fcatures and the expectod reward is crucial for effective learning and minimizing cumulative regret.
2.3 Combinatorial Bandits
Combinatorial multi-armed bandits (CMAB) (Cesa-Bianchi & Lugosi 2012) deal with problems where each time step i, a subset S, (called a super arm) of the set of all base arms A is selected, instead of individual arm. The reward of super arm S depends on its constituent base arms. When the reward for a super arm is given as a function (e.g., sum) of feedback from its individual base arms (observable if and only if the super arm is selected), it is referred to as semi-handil feedback. As previously, the evaluation metric is the cumulative regret, and for the combinatorial mani-bandit setting (with the sum of base arm feedback as super arm reward) it can be defined as
T R(T) &
Σ
Σ p4 - Σ H4
(2)
t=1
EES;
jES,
where Si denotes the optimal super arm at time
3 Proposed Algorithms
Machine learning models based on decision trees have consistently demonstrated solid performance across
various supervised learning tasks (Brrisvv et al.] 2022 Gorishniy al. 2021 Grinsztajn et al. 2022). An
3

---

Published in Transactions on Machine Learning Research (10/2024)
up-to-date overview of tree ensemble methods is provided by Blockeel et al. (2023) where several advantages are discussed over other techniques. For instance, they are known to learn fast from small sets of examples, while simultaneously possessing the capability of handling large data sets, and are computationally efficient to train.
Despite the potential benefits, these types of models have not been studied much for contextual bandits. To the best of our knowledge, there is no previously known work that in a principled way combines tree ensemble models with UCB, which is one of the most effective strategies known for handling the exploration- exploitation dilemmaa. Further, works that combine tree ensemble methods with Thompson Sampling are limited. We address this rescarch gap and introduce novel approach for the contextual MAB problem that combines any tree ensemble method with a natural adaption of these two prominent exploration schemes.
Within our framework, we empirically investigate the XGBoost and random forest algorithms and demon- strate promising performance on several benchmark tasks, as well as a combinatorial contextual MAB prob- lem for efficient. navigation over a stochastic road network in Section 4 However, we emphasize that our bandit algorithms are sufficiently general to be employed with any decision tree ensemble.
3.1 Tree-Based Weak Learners
The underlying concept of decision tree ensembles is to combine several weak learners. Each standalone tree is sufficiently expressive to learn simple relationships and patterns in the data, yet simple enough to prevent overfitting to noise. By combining the relatively poor predictions of a large number of weak learners, the errors they all make individually tend to cancel out, while the true underlying signal is enhancod.
In our notation, a tree ensemble regressor is collection of N decision trees {fn), where the trees are collectively fitted to set of training samples [(x,r)} Each sample consists of a context vector and a larget value The fitting procedure can differ between different types of tree ensemble methods, which are often divided into two categories based on the approach used, i.e. bagging or boosting. In both variants, the prediction of each tree is determined by assigning the training samples to distinct leaves, where all samples in the same leaf resemble each other in some way, based on the features attended to in the splitting criteria associated with the ancestor nodes of the leaf. Hence, when fitted to the data, each tree fn receives an input vector which it assigns to one of its leaves.
Every leaf is associated with three values that depend on the samples from the training data assigned to that particular leaf. We denote the output of the nth tree by On, which is this tree's contribution to the total ensemble prediction and depends on which leaf the input vector x is assigned to. The number of training samples assigned to the same lcaf as x in tree n is denoted by c.- Finally, the sample variance in the output proposed by the individual training samples assigned to the leaf is denoted 2 This value represents the uncertainty in the output On associated with the leaf and depends not only on the training samples but also on the particular tree ensemble method used. We elaborate on the calculations of s for two types of tree ensembles in Sections 3.6 and 3.7 Note that, for the sample variance to exist, must have at least two samples. This is ensured by requiring the tree to be built such that no leaf has fewer than two training samples assigned to it.
The tree ensemble constructs its total target value prediction p by summing up all of the N individual trees' outputs o,:
N p(x) = Σ (x).
(3)
The outputs On, in turn, are averages of the cn outputs suggested by cach training sample assigned to the same leaf. These suggested outputs are based on the target values of the training samples, with the calculation method depending on the specific type of tree ensemble used. We always consider the full tree ensemble target value predictions as a sum of the individual tree predictions o, to unify the notation of all kinds of tree ensembles. Hence, for averaging models, such as random forests, we assume that the leaf values On are already weighted by 1/N.
4

---

Published in Transactions on Machine Learning Research (10/2024)
3.2 Uncertainty Modeling
For bandit problems, keeping track of the uncertainly in the outcomes of different actions is crucial for guiding the decision-making process. In order to form estimates of the uncertainty in the final prediction of the tree ensembles we employ, we make a few assumptions.
Firstly, we assume that the oulput On of the n'th decision tree; given a context x, is an arithmetic average of cn independent and identically distributed random variables with finite mean pn and variance o By this assumption, On is itself random variable with mean Pn and variance d Also, can approximate pa Cn
and o by the sample mean and variance respectively, based on the training samples assigned to the leaf. Moreover, the central limit theorem (CLT) (see e.g., Dodge 2008) ensures that, as O2 + oo, the distribution of On tends to Gaussian distribution. See Appendix A.2 for more details about the independence assumption.
Secondly, if we also assumne the output of each one of the N trees in the ensemble to be independent of every other tree, we have that the total tree ensemble's target value prediction, which is a sum of N random variables, is normally distributed with mcan μ >>> H4 and variance x² = >>>, o?
We acknowledge that these assumptions may not always be true in practice, but they act here as motivation for the design of our proposed algorithms. Specifically, they entail a straightforward way of accumulating the variances of the individual tree contributions to obtain an uncertainty estimate in the total reward prediction, allowing us to construct efficient exploration strategies. In the following two subsections, we present our approach to doing so with UCB and TS methods, respectively.
3.3 Tree Ensemble Upper Confidence Bound
UCB methods act under the principle of optimism in the face of uncertainly, and have been established as some of the most prominent approaches to handling exploration in bandit problems. A classic example is the UCBI algorithm (Auer et al. (2022) which builds confidence bounds around the expected reward from each arm depending on the fraction of times it has been played, and for which there are proven upper bounds on the expected regret. One disadvantage of the method, however, is that does not take the variance of the observed rewards into account, which may lead to a sub-optimal exploration strategy in practice. In light of this, Auer et al. (2002) further proposed the UCB1-Tuned and UCB1-Normal algorithms, which extend UCBI by including variance estimates, and demonstrate better performance experimentally. The main difference between the two extended versions is that UCB1-Tuned assumes Bernoull--distibber rewards, while UCB1-Normal is constructed for Gaussian rewards. At each time step I, UCB1-Normal selects the arm a with the maximal upper confidence bound Ukas calculated as
In(t In)
Uta t- Bea + V 1607, M4,a
(4)
where my,a is the number of times arm a has been played so far, and Pe.e and 0ū,a are the sample mean and variance of the corresponding observed rewards, respectively. For the sample variance to be defined for all arms, they must have been played at least twice first.
By the assumptions we have made on the tree ensembles, the predictions of the expected rewards will be approximately Gaussian. Therefore, we propose an algorithm called Tree Ensemble Upper Confidence Bound (TEUCB) Algorithm D which draws inspiration from UCBI-Normal, and is suitable for both Gaussian and Bernoulli bandits. As soen in lines 27 and 31 of Algorithm [ the selection rule of TEUCB closely resembles that of UCBI-Nornal, but is constructed specifically for contextual MABs where the arms available in each time step are characterized by their context vectors. Therefore, TEUCB considers each individual contribution from all samples in leaf as a sample of that leaf's output distribution, which is demonstrated in line 14 The total prediction for a context Xt, is subsequently computed as the sum of sampled contributions from each leaf that Xt,a is assigned to in the ensemble (lines 16
18
Beyond yiclding better performance in experiments, there are additional benefits associated with considering the sample variances of rewards in the TEUCB method, as discussed regarding UCBI-Normal. Since each tree in the ensemble may be given different weight, certain trees can contribute more than others to the
5

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm Tree Ensemble Upper Confidence Bound / Tree Ensemble Thompson Sampling
Input: Number of rounds T, number of initial random selection rounds Tr, number of trees in ensemble N, exploration factor v, tree ensemble regressor f, bandit method (UCB TS). for t= 1 to T₁ do
Lan. Ct.a.n
At, Ot,a,n i,an Increment arm parameters:
15:
16:
Pt.e + Pr.e Pt,,
17:
of s- o o i,an
18:
Ct f Craa Ct,a,
3: Randomly select and play an arm dz
19:
end for
4: Observe context Xt,a, and reward Tt,,,
20:
if bandit method is UCB then
5: end for
Uto f Ae,o + v 1P02, In((-1) Cza
21:
for t = to do Fit tree ensemble to previously observed context-reward pairs {(xi,,, Ti,a;)) 1--1 and set leaf values
22:
else if bandit method TS then
23:
fr. ~ Ni v² o2
24:
end if
25: end for
8:
Observe current contexts {xt,)a=
26: if bandit method is UCB then
9: for a= 1 to K do
10:
Initialize arm parameters:
27:
+ argmax, Ut.
28: else if bandit method is TS then
Jta <- 0, L.a f- 0, Cta f- 0
11:
for n to N do
29:
0g <- argmax, Pr.a
30: end if
12:
Assign leaf values:
31: Play a, and observe reward ft,e
13:
(ot,a,n; St,a, Ct,a,n) + fn (Xt,a) Update leaf parameters:
32: end for
14:
final reward prediction. This should be accounted for in the lotal uncertainty as well, since it can otherwise dominated by high uncertainty estimates from trees low importance to the prediction. Accounting for the sample variances the proposed tree contributions individually is a way preventing such behavior.
3.4 Tree Ensemble Thompson Sampling
The way in which uncertaintics are estimated by TEUCB can also be incorporated into Thompson Sampling (Thompson I933). In its traditional form, Thompson Sampling selects arms by sampling them from the posterior distribution describing each arm's probability of being optimal, given some (known or assumed) prior distribution and previously observed rewards. This can be achieved by sampling mean rewards from each arm's posterior distribution over expected rewards, and playing the arm with the largest sampled mean reward.
Using a TS-based approach, we propose to estimate the uncertainty in the predicted reward given an arm's context in the same way as in the case with UCB. However, in line 23 of Algorithm ! instead constructing confidence bounds, we sample mean rewards from the resulting distributions (here, interpreted as posterior distributions). Hence, the main difference from TEUCB how the uncertainty used guide exploration. Due to its similarity with standard Thompson Sampling, we call this algorithm Tree Ensemble Thompson Sampling (TETS).
Regular Thomson Sampling is inherently Bayesian approach. However, the framework may be extended to include the frequentist perspective as well, and the two views have been unified in a larger set of algorithms called Generalized Thompson Sompling (Li 2013). It should be noted that TETS, as we present it here, is prior-free and should fall under the umbrella of Generalized TS. Although not the focus of this work, the algorithm could be modified explicitly incorporate and utilize prior beliefs, making it Bayesian in the traditional sense.

---

Published in Transactions on Machine Learning Research (10/2024)
3.5 Extension to Combinatorial Bandits
The framework outlined in Algorithm I is formulated to address the standard contextual MAB problem. However, TEUCB and TETS can easily be extended to the combinatorial semi-bandit setting. The main difference is in the way arms are selected, i.c., super arms instead of individual arms. In Algorithm I this
corresponds to modifying lines 27 lo
St + argmaxs Σ Urar aES
(5)
and 29 to
S. t argmax
Σ it. aES
(6)
The selected super arm S: at time / is subsequently played in line 31 In this setting, the set of observed context-reward pairs would include all rewards received for each base arm in the selected super arms indi- vidually, which are generally more than one per time step.
3.6 Adaptation to XGBoost
Extreme gradient boosting (XGBoost) is a gradient boosting algorithm that utilizes ensembles decision trees and techniques for computational efficiency (Chen & Guestrin 2016). Gradient boosting creates new decision trees based on the gradient of the loss function. The ensemble output is based on the cumulative contribution of the decision trees within the ensemble.
When using XGBoost regression models, we can extract o, directly from the individual leaves in the con- structed ensemble. The sample variance s is not accessible directly, but we can easily calculate it. As a GBDT method, XGBoost calculates its outputs during the training procedure as the average difference between the target value and the value predicted from the collection of preceding trees in the ensemble, multiplied with a learning rate. Hence, the trees do not have predetermined weights as in, e.g., random forests. Instead, the relative size of the contributions of assigned leaf to the final prediction depends the particular paths that are traversed through the other trees, which may be different for every sample we observe in leaf. Therefore, cannot estimale S from the variance in target values directly.
However, Xoooost is augmented with many useful features, one of them being staged predictions Boost Developers, 2022b). This mcans that we can propagate the predicted outputs on sub-ensembles up to a cerlain tree on all data samples and cache these outputs. After recording these we include the next tree in the prediction as well, without having to start over. By utilizing this technique, s2 is easily estimated from the previously observed samples assigned to particular leaf. Furthermore, C, is simply the number of such samples. This gives us all the pieces of the puzzle needed to apply XGBoost to the TEUCB and TETS algorithms. In order to reduce bias when calculating On, 8h and Gn, one may split the previously observed samples into two distinct data sets; one which is used for building the trees, and a second for the value estimations.
3.7 Adaptation to Random Forest
Random forest Ho 1995) is a supervised machine learning algorithm that utilizes decision trees as base learners together with bootstrapped aggregating (bagging). Bagging models randomly sample from the training data with replacement- reducing the variance of the model by providing the base learners with diverse subsets from the complete dataset. In addition to bagging, a random forest randomly samples a subset of the features (Hastic et al. 2009). For classification tasks, majority voting is commonly used to make predictions, while in regression, the average or weighted average of predictions is a common method.
Similar to XGBoost, random forests can also be incorporated into TEUCB and TETS. This is even less complicated in the case of random forests as the trees in random forest do not depend on the predictions made by any of the other trees. Therefore, 2² can be directly estimated from the variance in the target values, taking the tree's weight of 1/N into account. Hence, all the quantities of interest (i.e., On $2 and
7

---

Published in Transactions on Machine Learning Research (10/2024)
C.) are available from the trees of random forest by looking at which observed samples are assigned to the terminal nodes.
As with XGBoost, one may consider dividing the previously observed samples into different subsets for fitting and value estimation. An alternative way for handling bias with random forests is to consider only the out- of-bag samples for computing On: s4, and Gp- Random forests employ the concept of boaginn-rrsampling with replacement- when building trees, which means roughly one-third of the samples will be omitted in the construction of any particular tree. Thus, they yield natural way of providing an independent set of data samples for model evaluation without limiting the size of the training data set.
4 Experiments
In this section, we evaluate TEUCB and TETS and compare them against several well-known algorithms for solving the contextual bandit problem. For the implementations, & Guestrin 2016) to build gradient-boosted decision trees as our tree ensembles, as well as the version of random forests found in the scikit-learn library (Pedregosa et al., 2011). We first evaluate the algorithms on benchmark datasets. We then study them in the combinatorial contextual sctting for solving the real- world problem of navigation over stochastic road networks in Luxembourg The agent's cumulative regret is calculated by comparing the path to an oracle agent, who knows the expected travel duration for each edge given the current time of day, All the algorithms are evaluated w.r.t. cumulative regret averaged over ten random seeds and report the average results. The setup of the experiments is inspired by and adapted from Russo et al. 2018).
use the XGBoost library (Chen
4.1 Setup
We use the same procedure as Zhang al. (2021) to transform a classification task into a contextual MAB problem. In each time step, the environment provides context vector belonging to unknown class. For the agent, each class corresponds to an arm, and the goal is to select the arm corresponding to the correct class. This results in a reward of 1, while an incorrect prediction results in a reward of O.
Since only the context of a single (unknown) arm is provided, the agent must have a procedure for encoding it differently for each arm. This is generally done through positional encoding, where in the case of K arms and d data features, we form context vectors (cach of dimensionality Kd) such that: x1 = (x;0; ... :0), X2 x0; :0,,... X 0;..; ;x). As no features are shared between any of the arms, this setup is instance of disjoint model, opposed to hybrid model (Li al. 2010
In the experiments in Section 4.2 we use the disjoint model for LinUCB, LinTS, NeuralUCB, and NeuralTS. However, due to the nature of discrete splitting by decision trees, we can encode the context more effectively using a hybrid model for tree- based methods. There, we simply append the corresponding labels as a single character for each arm respectively at the beginning of the context: X₁. = (k, x), and mix numeric and catogorical features in the context vectors. For LinUCB, LinTS, NeuralUCB, and NeuralTS, categorical features are one-hol-encoded.
In these experiments, we set the time horizon to 10,000 (except for the Mushroom dataset, where horizon of 8,124 is sufficient to observe it entirely). For each of those time steps, the agents are presented with a feature vector x drawn randomly without replacement, which they encode for the different arms as described above. Subsequently, the agents predict the rewards for the individual arms according to the algorithms used. TEUCB and TETS (Algorithm 1 are described Section 3 The TreeBootstrap (Elmachtoub et al., 2017), NeuralUCB (Zhou et al. 2020). NeuralTS (Zhang al. 2021 p. LinUCB (Li et al. 2010)) and LinTS (Agrawal & Goyal 2013) algorit implemented according to their respective references.
4.2 Contextual Bandits
For this experiment, the data is collected from the UCI machine learning repository (Kelly et al. n.d.)). where an overview of the used selected datasets is given in Table [ Magic (Bock) 2007). which is short for Magic Gamma Telescope, contains only numerical features. The same true for Shuttle (Statlog (Shuttle).
8

---

Published in Transactions on Machine Learning Research (10/2024)
Table 1: Datasets overview.
Dataset
Features
Instances
Classes
Adult
14
48 25,842
2
Magic
10
19,020
2
Mushroom
22
8,124
2
Shuttle
9
58, 38,000
7
n.d.) also known as Statlog. All features of Mushroom [Mushroom 1987 are categorical, and Adult (Becker
& Kohavi 1996)
has a balanced distribution between mumerical and categorical features.
TreeBootstrap-XGBoor
cumulative regret
2000
TreeBootstrap RF TreeBootstrap-De
cumulative regret
2500
TEUCB-XGBoost
2000
1500
TETS-XGBoost
TEUCD-RF
TETS-RF
1500
1000
NeuraIUCB
NeuralTS
1000
LinUCB
500
LinTS
500
0
0
2500
5000
7500
10000
2500
5000
7500
10000
time step
time step
(a) Adult
(b) Magic
1250
cumulative regret
800
cumulative regret
1000
600
750
400
500
200
250
0
0
2000
4000
6000
8000
2500
5000
7500
10000
time step
time step
(c) Mushroom
(d) Shuttle
Figure 1: Comparison of contextual MAB algorithms UCT datasets. Figures la
1b
1c and
1d
share the
color scheme for consistency, but the legend is only prosented in la for improved visibility.
4.2.1 Implementation
For all datasets in Table I the neural network agents network architecture of one hidden layer with 100 neurons. Regarding NeuralUCB, NeuralTS, LinUCB, and LinTS, we scarch the same sets of hyper- parameters as described by Zhhng et al. (2021), who run these agents on the same dalasets, and select the parameters with the best performance. One difference our experiments is that we added a dropout probability of 0.2 when training the neural networks, which had a positive impact on the performance. Furthermore, each of the networks trained for epochs. For all tree ensemble bandits, we use XGBoost and random forest regressors with MSE loss and ensembles of 100 trees.

---

Published in Transactions on Machine Learning Research (10/2024)
Table 2: Average regret accumulated by agents after the final step, with standard deviation, and number of hours required run one experiment with CPU. Runtime in hours on GPU is also reported where applies.
Adult
Magic
Mushroom
Shuttle
TEUCB-XGBoott
Mean = SD CPU
1532.5 27.8
1685.7 27.7
69.2 8.6
171.4 = 40.0
0.13
0.14
0.09
0.08
TETS-XGBoost
Mean + CPU
1548.0 + 30.9
1703.2 25.2
78.6 1 11.8
165.7 = 31.2
0.13
0.14
0.09
0.08
TEUCE-RF
Mean = SD CPU
1550.6 + 32.9
1678.5 + 31.3
58.2 # 10.9
190.8 = 68.9
0.12
0.13
0.10
0.12
TETS-RF
Mean = SD
1566.3 + 34.2
1688.6 = 38.3
57.7 = 8.1
166.3 = 37.1
CPU
0.12
0.13
0.10
0.12
NeuralUCB
Mean = SD
1974.0
82.0 10
2135.2
39.5
160.8
68.9
862.4
428.8
CPU
10
7.4
8.1
GPU
1.2
0.68
0.37
1.4
NeuralTS
Mean + SD
1929.7 + 68.3
2209.5
62.2
243.4 E 168.9
853.8
340.3
CPU
10
10
7.4
8.1
GPU
1.2
0.68
0.37
1.4
LinUCB
Mean = SD
2109.8 + 51.8
2598.4 = 25.4
666.2 # 14.7
1156.3 # 41.3
CPU
0.02
0.02
0.04
0.11
LinTS
Mean + SD CPU
2253.2 + 37.7
2703.8 = 30.4
892.2 + 18.6
1263.0 + 22.1
0.02
0.02
0.04
0.11
TreeFoolstrap-XGRoooe
Mean + SD CPU
1693.2 + 18.8
1836.1
36.7
91.6 5.6
164.1 24.4
0.97
1.2
0.10
0.27
TreeBootstrap-Rtt
Mean 1 SD CPU
1584.3 + 32.5
1722.9 + 28.0
82.5 1 3.3
161.9
29.2
3.8
4.2
1.8
4.2
TheeBootstrappDT
Mean + SD CPU
2187.2 + 57.1
2473.3 = 35.3
168.9 + 11.0
216.0 = 22.9
0.08
0.09
0.04
0,08
Initial test runs revealed that the agents are robust w.rtt. different choices of (XGBoost Developers] 2022a), , and consequently, we settle on the default values. The only exception the maximum tree depth, which we set 10. The same maximum tree depth used for the implementation of random forests. The number of initial random arm selections Ty is set to 10 times the number of arms for all tree-based algorithms, and the exploration factor of TEUCB and TETS is set to 1. As for the decision tree (DT) algorithm used for TreeBootstrap, we use the scikit-learn library to employ CART (Breiman et al. 2017), which is free of tunable parameters. This is similar to the implementation presented in the original work on TreeBootstrap (Elmachtoub et al. 2017
for XGBoost
Another point we noted during our initial test runs was that accurate predictions seem be more important than less biased estimates obtained by splitting the previously observed samples into distinct data sets for ensemble fitting and value calculations respectively. Therefore, use all observed context-reward pairs for both purposes in all experiments with TEUCB and TETS.
In order to avoid unnecessary computations and speed up the runs, TEUCB and TETS do not build new tree ensembles from scratch at cach time step. Instead, they only consider which leaves the latest observation assigned in each tree and update the corresponding 0n, 82 and en parameters. Initially, when newly observed samples may have relatively large effect on the optimal tree ensemble, re-building happens more frequently. However, as the effect that the samples are expected have on the architectures degrades over time, less re- ru-buid takes place. More precisely, re-building happens when the function [8 [n)]]] increases by one compared to the previous time step.
The experimental results are obtained using an NVIDIA A40 GPU for NeuralUCB and NeuralTS, and a desktop CPU for the other agents. To illustrate the differences in computational performance between the agents, we report. the runtime of the neural agents on the same CPU as well.
4.2.2 Experimental Results
The results of the experiments deseribed above are presented in Fig. D and Table 2 tree ensemble methods consistently outperform all other models by large margin, both with XGBoost and
We observe that the
10

---

Published in Transactions on Machine Learning Research (10/2024)
TreeSp
Ire
60000
cumulative regret
40000
TreeBretiipp DT
cumulative regret
TEUCB XGBoost
50000
TETS -GB
30000
TEUCB TET5-4F
40000
NerratS
30000
20000
Liniccs
Un18
20000
10000
10000
0
200
400
600
800
1000
200
400
600
800
1000
time step
time step
(a) Cumulative regret on paths problem instance
(b) Cumulative regret on paths problem instance 2
Figure 2: Experimental results on real-world road network navigation in Luxembourg.
random forest, and yield significantly lower cumulative regrets. Furthermore, TEUCB and TETS tend perform better than TreeBootstrap on the adult, magic, and mushroom data sets.
On the shuttle data set,, with seven different arms, the TreeBootstrap agents exhibit comparable and even slightly better average performance in terms of regret minimization. It appears that TreeBootstrap's assign- ing of a separate tree-based model for each arm is beneficial for this problem. However, this comes at the expense of having to fit multiple models each time step, which is time-consuming and computationally de- manding. Furthermore,
inability to generalize the reward predictions of distinct. but related arms may some cases be disadvantageous, especially for larger arm sets. Comparing TEUCB vs. TETS, and XGBoost random forest (i.e., the different design choices within framework). there is clear winner they all tend to perform comparably (and very effectively) different data sets. In addition to regret minimization, the CPU experiments indicate that TEUCB and TETS are significantly more efficient than their neural counterparts from a computational perspective. Notably, LinUCB, LinTS, and TreeBootstrap-De are the most efficient methods terms of computation. However, they do not minimize regret as effectively as most other agents our data, sets.
4.3 Combinatorial Contextual Bandits
In this section, we investigate the combinatorial contextual bandit methods on a real-world application, where we study two scenarios corresponding to performing the most efficient navigation over the real-workd road network Luxembourg. This problem is crucial with the emergence electric vehicles to mitigate the so- called range anxicty. Similar navigation problems have recently been studied from a CMAB perspective, but often without contextual information (Akerblom al.] 2023) or limited to neural bandit methods (Hoseini et al. 2022). CMAB methods well-suited to the navigation problem since the traversal time of each road segment be highly stochastic and dependent local factors (e.g., road works, traffic congestion, stop lights) about which knowledge may be gathered through sequential interactions with the environment.
4.3.1 Implementation
We model the road network of Luxembourg via a graph 9(V,E), with | 2, 247 vertices and |ε| = 5, 651 edges. The vertices represent intersections in the road network, and the edges represent individual road segments connecting the intersections. In this scenario, edges correspond to base arms, and paths (i.e., ordered sequences of edges) correspond to super arms. Each vertex has a coordinate consisting of longitude, latitude, and altitude values. For all edges E E, the contextual vector x describes each road segment in the network. The agent. is presented with a vector containing uontext data according to Table 3
Edge traversal times have been collected using the Luxembourg SUMO Traffic (LuST) simulation scenario (Codeca et al. 2015). The recorded edge traversal times are used to form kernel density estimators (KDE) Weglarczyk] 2018 for each edge. If an edge does not contain any recorded traversals, the expected traversal
11

---

Published in Transactions on Machine Learning Research (10/2024)
Table 3: The variables included in the contextual vector describing each edge in the graph.
Variable
Description
Start position along x-axis.
Start position along y-axis.
Start position along z-axis.
End position along x-axis. End position along y-axis End position along 2-axis
1/
(a x²)
Euclidean distance along x-axis.
(y 2
Euclidean distance along y-axis. Euclidean distance along 2-axis. Maximum speed limit A boolean if edge includes stop The current time of day
(2 - 2²)²
speed limit
stop
time
time is set to the length of the edge divided by the speed limit, At each time step t, the time of day is randomly sampled, and used for updating the expected travel times of all edges and the corresponding KDE's. We generate edge-specific feedback by individually sampling travel times from the KDE of each edge the chosen path.
As the graph contains more than 5,000 edges, the agents need to learn how the contextual features impact the expected travel time. The road types in the graph are highways, arterial roads, and residential streets, with a total longth of 955 km. In our experiments, we specifically study two problem instances (characterized by different start and end nodes), referred to as problem instancee and problem instance 2. The paths selected by the different agents during a single run are visualized for problem instance 1 in Fig. 3 (in the Appendix).
An agent predicts the expected travel time for each of the edges in the graph, and then solves the shortest path problem using Dijkstra's 's algorithm (Dijkstra 1959). The agents are evaluated based on the sum of the expected travel times for all edges forming the traversed path compared to the expected travel time of the optimal path S
For this experiment, the neural agents utilize a neural network with two hidden layers, both containing 100 fully connected neurons. A dropout probability of 0.2 is used and after a parameter search over the same sets of values as in Section 4.2.I we set À 0.1 and v 0.001. Furthermore, the network is trained over 10 epochs with the option of early stopping if the MSF loss does not tend to keep improving. We implement the tree ensemble bandits utilizing XGBoost and random forest regressors with maximum tree depths of 10; all other agents with Iree ensembles, and the initial random selection is set. to T₁ = 10 paths. An exploration factor of / = is used for TEUCB and TETS and the frequency of re- building their tree ensembles the same as described in Section 1.2.1
being set to their default values. The mumber of trees is set to N = 100 for all
4.3.2 Experimental Results
Fig. 2 shows the results of the TEUCB and TETS methods along with the baselines. The road network and the agents' traversals are presented in Fig. 3 (in the Appendix). The frequency by which an edge has been traversed is indicated by the red saturation, where more traversals correspond to a higher saturation. is worth noting that LinUCB, LinTS, and the TreeBootstrap require excessive exploration as their models are odge-specific. In contrast, TETS, TEUCB, NeuralTS, and NcuralUCB train one model with the possibility of generalizing the expected travel time predietions over different edges. We observe that using both XGBoost and random forest, TEUCB and TETS significantly outperform the other methods. In this setting, if an agent can generalize well what it has learned from one arm's reward distribution to the other arms, it can then effectively avoid over-exploration, as indicated by both the regret plots in Fig. and the agent's 's specific path selections in Fig. 3 Comparing the two different tree ensemble methods, XGBoost. seems to perform better on the navigation task compared to random forests in the TEUCB and TETS frameworks.
The neural methods tend outperform LinUCB and LinTS. Compared to TreeBootsrrap, however, the advantage is less clear, and seems to depend on the particular time horizon T. NeuralUCB and NeuralTS
12

---

Published in Transactions on Machine Learning Research (10/2024)
tend to learn faster, which is unsurprising since they generalize reward predictions over different specific arms. After an initial period of heavy exploration, however, the TreeBootstrap agents appear to make good path selections more frequently, and yield cumulative reward curves that are more similar to those of TEUCB and TETS in slope.
All the agents were run on a single desktop CPU, apart from NeuralUCB and NeuralTS, which were run on an NVIDIA A40 GPU. NeuralTSS and NeuralUCB tend to require highly parameterized networks and substantial prrer-parammter tuning to achieve deliberate exploration, which can make them time-consuming while running and searching for good parameter values. In terms of runtime, the experiments took about an hour on the GPU for a neural agent. It is also noticeable that the neural agents appear to be sensitive to the weight initialization of the nelworks, which leads to higher variance (see Fig, 2 In contrast, TETS and TEUCB achieve solid results for a large range of parameter settings, yield lower regret, and tend to run at comparable speed on a single CPU (instead of GPU). The experiments with TEUCB and TETS took about 1.5 hours with XGBoost, and hours using random forests as the tree ensemble methods. The runtime of Tree also lends to depend heavily on the particular tree model used. With single decision tree per arm, the experiments took 0.5 hours, which is about the same LinUCB and LinTS, Using tree ensembles, they took about 4 and 20 hours with XGBoost and random forests, respectively.
5 Conclusion
We developed a novel framework for contextual multi-armed bandits using tree ensembles. Within this framework, we adapted the two commonly used methods for handling the exploration-cxplottatiee UCB and Thompson Sampling. Furthermore, we extended the framework to handle combinatorial contextual bandits, enabling more complex action selection at each time stop. To demonstrate the effectiveness of the framework, we conducted experiments on benchmark datasets using the XGBoost and random forest tree ensemble methods. Additionally, we employed it for navigation over stochastic real-world road networks, modeled as combinatorial contextual bandit problem.
dilemma:
Across all problem instances, the introduced tree ensemble-based methods, TEUCB and TETS, consistently demonstrated effectiveness in minimizing regret while requiring relatively low computational resources. In many cases, these methods significantly outperformed neural network-basod methods that are often consid- ered state-of-tho-art for contextual bandits, in terms of both accuracy and computational cost. Hence, this work indicates that using tree ensembles offers several advantages over other machine-learning models for these problems. Furthermore, compared to other tree-based methods, TEUCB and TETS exhibited similar or better capabilitics in minimizing regret while maintaining computational efficiency, even for problems with large numbers of arms. These results indicate that using a single tree ensemble to predict the reward dis- tributions of all arms, particularly as implemented in TEUCB and TETS, facilitates effective generalization between arms based on context, enabling more efficient learning with fewer samples.
The study primarily focuses on the practical applicability of tree ensembles for bandits in various settings, Therefore, did not provide a theoretical analysis of the respective regrets. For future work, exploring theoretical regret bounds for the proposed tree ensemble methods could offer deeper insights and better understanding of the methods presented in this work.
Acknowledgments
The computations and data handling were enabled by resources provided by the National Academic Infras- tructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725. The work of Niklas Åkerblom was partially funded by the Strategic Ve- hicle Research and Innovation Programme (FFI) of Sweden, through the project EENE (reference number: 2018-01937).
13

---

Published in Transactions on Machine Learning Research (10/2024)
References
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvari. Improved algorithms for linear stochastic bandits. In Neural Information Processing Systems, 2011. URL http:::/app..eeatttiiccc semanticschollrr org/CorpusID: setaaatriiscccoo...ooororooroop
1713123
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with lincar payoffs. In Pro- ceealnngs of the 30th International Conference on Machine Learning, Proceedings of Machine Learning Research, pp. 127-135, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
Niklas Akerblom, Yuxin Chen, and Morteza Haghir Chehreghani. Online learning of energy consumption for navigation of electric vehicles. Artificial Intelligence, 317:103879, 2023. doi: 10.1016/j.artini 2023.103877
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit, problem. Machine Learning, 47(2):233-22) 256, 2002. ISSN 1573-0565. doi: 10.1023/ A:101388970435..
Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. URL https://doi.org org/
10. 20.24432/C5XXD
Hendrik Blockeel, Laurens Devos, Benoit Frénay, Géraldin Nanfack, and Siegfried Nijssen. Decision trees: from efficient prediction to responsible ai. Frontiers in Artificial Intelligence, 6, 2023. 1SSN 2624-8212.
R. Bock. MAGIC Gamma Telescope. UCI Machine Learning Repository, 2007. URL https://aoi.org
10. 20432442222222 CC52CBB
Vadim Borisov, Tobias Leemann, Kathrin Sessler, Johannes Haug, Martin Pawelezyk, and Gjergji Kasneci. Deep neural networks and tabular data: A survey. IEEE Transactions on Newral Networks and Learning Systems, pp. 1-21, 2022. ISSN 2162-2388. doi:
Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone Classification And Regression Trees. 10 2017. ISBN 9781315139470.
doi: 10.1201 /970/119111559770
Nicolò Cosa-Biancha and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 7805):1404-1422, 1422, 2012. ISSN 0022-0000.
doi: se10066/.jess.212.m..
JCSS Special Issue: Cloud
Computing 2011.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In J. Shawe Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger (eds.), Advonces in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011. URL http:///////ceeiiggg..ooo wwwpsen.n.r.r.ooeeeee.eeeee campperffllssse files/paper/
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16. ACM, 2016. doi:
Lara Codeca, Raphael Frank, and Thomas Engel. Luxembourg sumo traffic (lust) scenario: 24 hours of mobility for vehicular networking research. In 2015 IEEE Vehicular Networking Conference (VNC), pp. 1-8, 2015. doi: 241100//VNC.201..3385558
E.W. Dijkstra. A note two problems in connexion with graphs. Numerische Mathematik, 1:269-271 1959.
Yadolah Dodge. The Concise Encyclopedia of Statistics, pp. 66 68. Springer New York, New York, NY, 2008. ISBN 978-0-387-32533-1, doi: 00.1007/978-0-387-225 500
Adam N Elmachtoub, Ryan McNellis, Sechan Oh, and Marek Petrik. practical method for solving con- textual bandit problems using decision trees. arXiv preprint arXiv:1766 04687, 2017.
Raphaël Féraud, Robin Allesiardo, Tanguy Urvoy, and Fabrice Clérot. Random forest for the contextual bandit problem. In Proceedings of the 19th International Conference on Artificial Intelligence and Statis- tics, volume 51 of Proceedings of Machine Learning Reseorch, pp. 93-101, Cadiz, Spain, 09-11 May 2016. PMI.R.
14

---

Published in Transactions on Machine Learning Research (10/2024)
Yury Gorishniy, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko. Revisiting deep learning models for tabular data. In Aduances in Neural Information Processing Systems, pp. 18932-1888 18943. Curran Associates, Inc., 2021.
Leo Grinsztajn, Edouard Oyallon, and Gael Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? In Advances in Neurol Information Processing Systems, pp. 507 520. Curran Associates, Inc., 2022.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference and prediction. Springer, 2 edition, 2009.
Tin Kam Ho. Random decision forests. In Proceedings of 3rd international conference on document analysis and recognition, volume 1, pp. 278-282. IEEE, 1995.
Fazeleh Sadat Hoseini, Niklas Akerblom, and Morteza Haghir Chehreghani. A contextual combinatorial semi-bandit approach to network bottleneck identification. CoRR, abs/2206.08144 2022. doi: 10.48550/ ARXIV 22KIVV2200..8144.
Markelle Kelly, Rachel Longjohn, and Kolby Nottingham. The uci machine learning repository, n.d.
Lihong Li. Generalized thompson sampling for contextual bandits. ar preprint arXiv: 7163,, 2013.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire, A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web. ACM, 2010. doi: (1.1145/177690.111
Xinyuan Lu and Benjamin Van Roy. Ensemble sampling. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2017.
Mushroom. UCI Machine Learning Repository, 1987. URL
lan Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi, Xiuyuan LuI, and Benjamin Van Roy. Epistemic ncural networks. arXiv preprint arXiv:2107.08922, 2021.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Math. Oper. Res., 39(4):
1221-243, 2014.
Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. Found. Trends Mach. Learn., 11(1):1-900 96, jul 2018. ISSN 1935-8237. doi: 10.1561 /2000002000000000. URL
Aleksandrs Slivkins. Introduction to multi-armed bandits. Foundations and Trends0 in Machine Learning, 12(1-2):1-286, 2019. ISSN 1935-8237. doi: 10.1561 11156112200000068.
Statlog (Shuttle). UCI Machine Learning Repository, n.d. URL http:///b0i.rrg//0.244/////
William R. Thompson. On the likelihood that one unknown probability excoods another in view of the
evidence of two samples. Biometrika, 25(3/4):285 294, 1933. ISSN 00063444.
Stanislaw Weglarczyk. Kernel density estimation and its application. ITM Web of Conferences, 23:00037, 2018. doi: 10.1051 /2000///immoof/2002300333
XGBoost Developers. Xgboost documentation: Parameters.
http:://sboctt.eeethhdddss.ddd
stable/parameter html 2022a. [Accessed 2024-02-09).
XGBoost Developers. Xgboost documentation: Prediction.
http:///gbost.rratthdlcc.....
stable/predd.ction..m. 2022b. [Accessed 2024-02-09).
15

---

Published in Transactions on Machine Learning Research (10/2024)
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference on Learning Representations, 2021.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based exploration. In Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 11492-11502. PMLR, 13-18 Jul 2020.
Zheqing Zhu and Benjamin Van Roy. Scalable neural contextual bandit for recommender systems. Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM '23, pp. 3636 3646, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701245.. doi: 00.144/3583780..2
16

---

Published in Transactions on Machine Learning Research (10/2024)
A Appendix
A.1 Nomenclature
Table 4: Table of notations used in this paper.
Notation
Description Arm/action
Optimal arm
Arm selected time step
Action space, set of arms leaf in regression tree n
On
Number of training samples assigned
Tree ensemble regressor consisting of N regression trees fitted unison nth individual tree the ensemble
fn
mi.a
Number of times arm has been selected up to time step
N(a,
Normal distribution with mean and variance o²
On
Output value associated with a leaf in regression tree n Function of expected reward Observed reward
Estimsted reward
R
Regret
Sample variance of the output value associated with leaf in regression tree Super arm, set of arms
S*
Optimal super
super selected time step
time step
Upper confidence bound
Context/leature vector
True mean
Estimated mean
Exploration factor
True variance
Estimated variance
{3,)
List of entries
A.2 Further Elaboration on the Independence Assumption
Given a tree ensemble f = (11 f2.... JNv, the prediction for a context vector x is the sum individual
tree outputs:
p(x) Σ (x),
(7)
where each ox(x) a random variable representing the output of tree i when the input x. Assuming o (where e, is the number of training samples
the output of each tree ox( has mean b4 and a variance assigned to the leaf of tree that x ends in), the variance of the ensemble's prediction is:
Var(p(x)) Var Σ ox((x)
(8)
Under the independence assumption between the trees, the variance of the sum is simply the sum of the variances of the individual trees:
N Var(p(x)) = Σ Var(o;(x)) = Σ
N
(9)
i=1
17

---

Published in Transactions on Machine Learning Research (10/2024)
This expression allows us to estimate the total uncertainty in the ensemble's prediction by summing up the individual uncertainties of each tree.
In reality, especially in boosting algorithmss there might be some correlation between the trees. Let us denote the correlation between the outputs of two trees and j as Pij. The variance the sum of tree outputs in the presence of correlations becomes:
N-1 Σ :=1 j=
of
of Cj
Var(p(x))
+2
Pij
(10)
Here, Pi represents the correlation coefficient between the outputs of trees i and j. If the correlations Pij are positive, they increase the total variance of the ensemble's prodiction. However, if we assume independence (pij = 0), the second term vanishes, simplifying the variance to just the sum of individual variances, i.e.,
Var(p(x))
(11)
In the context of bagging- based ensembles like random forests, where trees are trained on different subsets of data and with random feature selection, the correlations Pij are typically small, making this approximation reasonable. For boosting-based methods, which sequentially fit trees, the correlations might be stronger, implying that our approximation could be less accurate.
However, we argue that this approximation often yiclds a lower bound for the actual variance, where this lower bound provides useful insights into the ensemble's uncertainly, offering simplified way to quantify prediction variability. For this, argue that negative correlations less common than positive ones in ensemble learning primarily due to the nature of how individual models are trained and how ensemble methods perform.
In tree ensemble methods, individual models (e.g., decision trees) are trained on subsets of the same data and tend to capture underlying patterns that are common across these subsets. This shared learning process often leads to similar predictions, resulting in positive correlations. In boosting, in particular, trees are added sequentially, with each new tree focused on correcting the errors (residuals) of the previous ensemble. As the boosting process continues, new trees are highly dependent the carlier trees' mistakes. Although boosting can somelimes create predictions that 'pull' in opposite directions (implying a negalive correlation locally), the overall direction of learning is typically aligned to reduce residual error. This alignment contributes to positive correlations because all trees are ultimately working together to approximate the same target function. Therefore, we can assume that in boosting, the overall correlation positive. On the other hand, as mentioned, bagging methods such as random forests use randomness (bootstrapping data samples and feature selection) to reduce the correlation between individual trees (i.e., the correlations can be discarded).
In summary, expect the independence assumption between the trees (i.e., Psj = 0) to hold reasonably well for bagging methods. On the her hand, this assumption usually leads to an underestimate of the total variance for boosting methods. This means that our calculated variance: > oi
ez serves as a lower bound on the true variance. Interestingly, some bandit algorithms, such as UCB, are known to suffer from over- exploration (Russo Roy] 2014), and thus underestimating the variance could even be helpful to mitigate this issue and lead to more efficient learning.
18

---

Published in Transactions on Machine Learning Research (10/2024)
A.3 Calculating Leaf Values
The code blocks presented in this section outline the procedure by which the leaf values dnd, sn and Co, for leaf/ / in tree are obtained for the implementation of TEUCB and TETS with XGBoost and random forests, respectively.
Algorithm Set Leaf Values XGBoost
Input:
Tree ensemble regressor f. number of 7: Get. prediction on x; from previous trees: in ensemble N, base predictor value learning rate " set of D training data points (x)):
Pn-1= E)=1 (x,)
On,l.e.. nr; Pn-1)
end for
2: On,,, Sn,1, Cn.1 = 0
4 trees n, leaves
10: end for
3: for i = 1 to D do
11: for n = 1 to N do
4: for n = to N do Check which leaf that the context x; is as-
12: for leaves I in tree n
do 2 nnn On.ii
13: On,1 En.i
signed to in tree Cr.1 Cr.! +1
$ 6n,1 Eimi (Ondi 0n,1)
15: end for
16: end for
Algorithm Set Leaf Values Random Forest
Input: Tree ensemble regressor f. number of trees in ensemble N, set of D training data points ((x)))))))
7: Onleen, = fz(x;)
end for
end for
2: On,1, Cr. = 0
A trees leaves
10: for n == to N do
3: for i to D do
11:
for leaves / in tree n do
4: for nl n= to N do
12: On,1 1 -iz On
c..
5: Check which leaf I that the context x, is as-
13:
$ ",,, i (On,1, On.1)
signed to in tree Cn. Gr.
14: end for
15: end for
19

---

Published in Transactions on Machine Learning Research (10/2024)
A.4 Path Selections
In this section, we present maps of the routes selected by the respective agents throughout one run of the navigation task.
(a) Optimal paths
(b) LinUCB
(c) LinTS
(d) TreeBootstrap-XGGBB Booos.
(e) TEUCB-XGBoos
(I) TEUCB-RF
(g) NeuralUCB
(h) TreeBootstrap-RI RF
(i) TETS-XGBoost
(i) TETS-RF
(k) NeuralTS
(I) TreeBootstrap-DT
Figure 3: The road network of Luxembourg shows the trajectories of different agents for the experiment on problem instance 1, where the corresponding cumulative regret is presented in Fig. 2a The plots show all the paths selected by the agents during a full run the experiment, where a higher level of opacity indicates that road segment was more frequently part of a traveled path.
20

---

Published in Transactions on Machine Learning Research (10/2024)
A.5 Sensitivity Analysis
Here, we investigate the robustness of TEUCB and TETS to changes in number of key (hyper)paramelers. To do so, we run the same experiments as presented in Section 4.2 but varying one parameter at time. In addition, we study how robust the methods are to delays in reward foodback, and compare the performance of TEUCB and TETS to TreeBootstrap.
A.5.1 Delayed Feedback
As done by Zhang et al. (2021) in the experiments with delayed feedback presented in Fig. 4 the rewards associated with an agent's s actions are fed in batches of varying batch size, rather than one by one instantly after the action taken. This setting appears to occur naturally in several real-world applications of multi- armed bandits, as discussed by Chapelle & Li (2011). Their findings suggest that Thompson Sampling scales better with delay in rewards than UCB methods, which also supportod by the experiments of Zhang et al.) h2021). It is not clear from our experiments whether this is the case for TEUCB, TETS, and Bootstat (which, discussed in Section I.1 can be viewed Thompson Sampling method). Comparing with the results of /Zhang et al. (2021) h for NeuralUCB and NeuralTS on the same datasets, however, it appears that the tree- based methods we study are more resilient to delays in the rewards.
A.5.2 Varied Tree Depth
In Fig. 5 we study the robustness of TEUCB and TETS towards different depths for the regression trees in the ensembles. We observe that significant change in tree depth may influence the performance of TEUCB and TETS when used with both XGBoost and random forests. We note that random forests tend to benefit from deeper trees, while XGBoost performs better with shallower ones. This is particularly interesting as the depth is only a maximum value for XGBoost, and the algorithm designed to automatically prune trees where deemed beneficial for the reduction of overfitting. The exlent to which this is utilized can be controlled by changing the XGBoost parameters y and X, though we use the default values. As a final note on the effect of tree depth, observe that depth of 10, which is used in the comparison study in Section 4.2 is suitable.
A.5.3 Varied Ensemble Size
In Fig. f we study how the performance of TEUCB and TETS varies with different numbers of trees making up the tree ensembles used to predict rewards. In this study, we that initially going from relatively small ensemble of trees to a larger one can greatly improve the performance, which makes sense. However, after this initial setup, the results stay stable when increasing the number of trees further. XGBoost appears to be particularly sensitive to selecting too few trees. This issue may potentially be mitigated by adjusting the learning rate parameter though we have not investigated this. Further, we note that setting the number of trees to 100, as in the comparison with other bandit mothods in Scction 4.2 is shown to be a good choice.
A.5.4 Varied Exploration Factor
Finally, in Fig. f we investigate the robustness of TEUCB and TETS to different exploration factors used to control the level of exploration. The results demonstrate that the methods are robust to changes in the exploration factor within a wide range of values. Only one observation deviates significantly from the pattern, in which an exploration factor of 100 used for TEUCB with XGBoost. For both datasets, this value results significantly larger average cumulative regret compared to all other evaluated methods and parameter values. For all other values and agents, the results are stable and consistent.
21

---

Published in Transactions on Machine Learning Research (10/2024)
600
TEUCB-XGBoost
TEUCB-RF
TETS-XGBoost
500
TETS-RF
TreeBootstrap-xGBoost
TreeBootstrap-RF
cumulative regret
400
TreeBootstrap-TT
300
0
100
500
1000
reward delay
(a) Cumulative regret with different levels of reward delays on the mushroom dataset.
2400
2200
cumulative regret
2000
1800
1600
100
500
1000
reward delay
(b) Cumulative regret with different levels of reward delays on the adult dataset
Figure 4: Comparison of TEUCB, TETS, and TreeBootstrap on the mushroom and the adult datasets with different levels of delays. Cumulative regret for a single experiment is calculated over 10,000 time steps and repeated 10 times. The results display the average cumulative regret plus/minn the standard deviation for each respective agent. Hyperparameters are selected as Section 4.2 All agents are evaluated on the same levels of reward delays, but each agent is shifted slightly horizontally for visualization purposes.
22

---

Published in Transactions on Machine Learning Research (10/2024)
BEUCB-XGBood
140
TEUCB-RI RF
TETS-XGBoOst
TETS-RF
120
cumulative regret
100
80
5
10
20
tree depth
(a) Cumulative regret with varying tree depths on the mushroom dataset
1800
1750
cumulative regret
1700
1650
1600
1550
1500
10
20
tree depth
(b) Cumulative regret with varying tree depths on the adult dataset
Figure 5: Comparison of TEUCB and TETS on the mushroom and the adult datasets with different tree depths. Cumulative regret for a single experiment is calculated over 10,000 time steps and repeated 10 times. The results display the average cumulative regret plus/minus /minus the standard deviation for each respective agent. Hyperparameters other than tree depth are selected as Section [.2] All agents are evaluated with the same tree depths, but each agent shifted slightly horizontally for visualization purposes.
23

---

Published in Transactions on Machine Learning Research (10/2024)
TEUCB-XGB XGBoost
TEUCB-RF
250
TETS-XGBoost
TETS-RF
cumulative regret
200
150
100
10
20
50
100
200
number of trees
(a) Cumulative regret with varying ensemble sizes the mushroom dataset
1800
1750
curulaative regret
1700
1650
1600
1550
1500
20
50
100
number of trees
(b) Cumulative regret with varying ensemble sizes the adult dataset
Figure 6: Comparison of TEUCB and TETS on the mushroom and the adult datascts with different numbers of trees in the ensembles.. Cumulative regret for a single experiment is calculated over 10,000 time steps and repeated 10 times. The results display the average cumulative regret plus/ minus the standard deviation for each respective agent. Hyperparameters other than the numbers of trees are selected as in Section [.2] All agents are evaluated with the same number of trees, but cach agent is shifted slightly horizontally for visualization purposes.
24

---

Published in Transactions on Machine Learning Research (10/2024)
BEUCB-XGBoOsE
TEUCB-RF
120
TETS-XGBoost
TETS-RF
100
cumulative regret
80
60
40
0.01
0.10
1.00
10.00
100.00
exploration factor
(a) Cumulative regret with varying exploration factors on the mushroom dataset.
1640
1620
1600
cumulative regret
1580
1560
1540
1520
1500
0.01
0.10
1.00
10.00
100.00
exploration factor
(b) Cumulative regret with varying exploration factors the mushroom dataset
Figure 7: Comparison of TEUCB and TETS the mushroom and the adult datasets with different explo- ration factors. Cumulative regret for single experiment is caleulated over 10,000 time steps and repeated 10 times. The results display the average cumulative regret plus/minus the standard deviation for each re- spective agent. Hyperparameters other than the exploration factor are selected as in Section 4.2 All agents are evaluated on the same exploration factors, but each agent shifted slightly horizontally for visualization purposes.
25


Reviews:
[{"review_id": "EhfIUCvshO", "reviewer": "Reviewer_wcpK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1. The methods for estimating posterior distributions around tree classifiers are novel and interesting, even if they are only heuristics.\n2. Their experiments are thorough, both in terms of tasks and baseline methods against which they compare, but see \"weaknesses\" for the limitations of these experiments\n\n**Weaknesses:**\n\n1. The biggest weakness is in section 4.3, which presents the results of TEUCB and TETS in the Luxembourg roads domain.  While the proposed methods appear to perform substantially better in this setting, I have a number of concerns about the validity of the results.  Looking at figure 3 in appendix A.2, it appears that none of the methods are sampling sensible routes between the given start and end locations.  In addition to being far longer than the optimal path shown in figure 3a, they appear to contain loops, which should be impossible if they were generated using Dijkstra's algorithm.  I can think of two possible explanations for this:\n    1. These figures (aside from 3a) show *all* road segments sampled by each of the learners during the training process (if so, this needs to be made clear)\n    2. There is no restriction on the models preventing them from predicting *negative* edge lengths, causing their implementation of Dijkstra's algorithm to return nonsensical looping paths\n2. The contextual bandit results in section 4.2 are also problematic.  In all but one of the tasks (the shuttle task), the number of classes, and therefore the number of arms, is only 2, suggesting that the exploration problem is somewhat limited.  Interestingly, the one problem where the proposed TEUCB and TETS methods are outperformed by the existing TreeBootstrap method is also the one problem in Section .42 with more than 2 arms, where improved exploration should be most helpful.  See the \"requested changes\" section for suggestions on how these issues could be addressed.\n3. The methods for building posterior distributions around the XGBoost and Random Forest classifiers are *heuristic*, that is, they would not accurate under any reasonable assumption about the data generating process.  While this is not an issue itself, the heuristic nature of the estimates should be stated explicitly, and the methods should be presented separately for the XGBoost and RF classifiers, as these are very different methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents novel methods for constructing confidence intervals around the predictions of tree-based classifiers and regression models, and apply these to contextual bandit problems, as well as a \"structured\" combinatorial bandit problem.  They present two methods for constructing (Gaussian) posteriors over the outputs of tree models, one for XGBoost trees, and one for Random Forests (RF).  They then apply these posteriors for both upper confidence bound (UCB) and Thompson sampling (TS) exploration in bandit settings.  They compare these methods against previous contextual bandit methods that use linear, neural, and tree-based (TreeBootstrap) classifiers, and find that they generally outperform these baselines in terms of total accumulated utility (or cost).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In Section 4, for each experiment, indicate how many initial samples $T$ were used to initialize the models\n2. Also, for the experiments in Section 4.2, estimate the *exploration rate* as a function of time.  This is the fraction of contexts in which the learner chooses an arm that does not maximize the expecteed return predicted by the model.  Also, estimate the error rate of the learner model as a function of time.  It is currently difficult to assess whether differences in performance are due to the amount of time it takes for exploration to stop altogether, or whether it has more to do with the accuracy of the learned models themselves.\n3. Check that the travel time predictions in Section 4.3 are lower-bounded by some reasonable value (or even just clipped to be non-negative).  Also, explain whether figure 3 shows a single sampled path for each learner, or the total set of road segments explored by those methods throughout the learning process.\n4. Include separate algorithm blocks for the construction of the posterior distributions for XGBoost and RF, as it appears that the pseudocode in algorithm 1 may not cover XGBoost exactly as it is described in the text.  Also, describe these algorithms separately in text.\n5. Include short explanations of XGBoost and Random Forests in the Background section (Section 2).", "broader_impact_concerns": "I identified no future ethical concerns arising from this work that would need to be addressed in the text.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lPwrVUEQOF", "reviewer": "Reviewer_2NeU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n* The use of tree ensemble models for contextual bandit problems is a creative and practical idea.\n* The methods appear to be more computationally efficient than the neural-based approaches [3,4].\n\n**Weaknesses**\n* The paper is purely experimental and lacks formal theoretical guarantees, particularly regret bounds for the proposed methods. This is a significant limitation compared to other bandit algorithms, where theoretical guarantees are often a key feature, e.g., [1,3,4]. Without theoretical support, it's unclear how well the methods generalize beyond the datasets tested. This raises concerns about the robustness of the approach in different scenarios or real-world applications.\n* The author's makes strong assumptions about the independence of trees in the ensemble and the Gaussian distribution of their predictions, which may not hold in practice. This assumption seems to made by convenience for the following UCB/TS. The authors acknowledge this but do not sufficiently explore the impact of these assumptions.\n* The pseudo-code in Algorithm 1 is overly basic. It would be beneficial for the authors to provide detailed pseudo-code for both TEUCB and TETS, including all the relevant hyperparameters, to make the methods clearer and easier to replicate.\n* The paper lacks publicly available code, which is critical for verifying and reproducing the results, especially in an empirical study.\n* The experiments, while useful, are limited in scope. Testing the methods on a broader set of datasets, particularly those with more challenging characteristics (e.g., delayed rewards [3]), would help assess the robustness and generalizability of the approach.\n* A sensitivity analysis of key hyperparameters (e.g., tree depth, number of trees, exploration factor) would provide readers with more practical insights into the robustness of the methods.\n\n**References**\n* [1] Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari. Improved algorithms for linear stochastic\nbandits. In NeurIPS, 2011.\n* [2] Emilie Kaufmann, Olivier Cappe, and Aurelien Garivier. On Bayesian Upper Confidence Bounds for Bandit Problems. In AISTATS, 2012.\n* [3] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In ICLR, 2021\n* [4] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based exploration. ICML, 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose applying tree ensemble methods to model the rewards in contextual multi-armed bandits (MAB). They introduce two algorithms—Tree Ensemble Upper Confidence Bound (TEUCB) and Tree Ensemble Thompson Sampling (TETS)—that adapt tree ensemble models, such as XGBoost and random forests, to this setting. the paper is purely experimental and lacks formal theoretical guarantees, such as regret bounds, which are common in bandit literature. While it is unsurprising that tree ensemble methods can outperform neural-based approaches in certain settings, neural-based methods [3,4] have the advantage of offering theoretical guarantees, which this work does not provide.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Major concerns**\n* See the weaknesses section above.\n\n**Minor concerns**\n* The authors should cite [1] when talking about LinUCB.\n*  While the authors explore UCB and Thompson Sampling, they do not investigate the possibility of extending their work to include BayesUCB [2], which could add further depth and relevance.\n\n**References**\n* [1] Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari. Improved algorithms for linear stochastic\nbandits. In NeurIPS, 2011.\n* [2] Emilie Kaufmann, Olivier Cappe, and Aurelien Garivier. On Bayesian Upper Confidence Bounds for Bandit Problems. In AISTATS, 2012.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rG052nGajq", "reviewer": "Reviewer_WzFc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This work is well written and easy to follow.\n2. Using tree ensembles is an interesting idea to improve the efficiency of bandit algorithms.\n\nWeaknesses:\nThe regret bound is missing, even under the unrealistic assumptions made in page 4. I think nowadays for bandit research it is indispensable to deduce a valid regret bound under some milder assumptions (i.e. no assumption on the leaves directly). Otherwise, any state-of-the-art supervised learning algorithms can be directly implemented before the UCB or TS, and hence the novelty is limited. On the other hand, all the existing tree-based bandit algorithms are somehow inefficient in practice since their invention have to deal with the theoretical regret bound simultaneously, which is the most difficult part of research. Therefore, it is not fair to compare the algorithms in this paper with those baselines directly.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a new framework for contextual multi-armed bandits based on several efficient tree ensemble methods, and it uses the classic upper confidence bound and Thompson sampling methods to draw the arm after tree fitting. Compared with some existing methods, the proposed algorithms can yield better performance in cumulative regret with less running time in a suite of benchmark datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be better if the authors could add some theoretical bounds for the proposed algorithms.", "broader_impact_concerns": "No negative societal or ethical impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The only main concern that some reviewers continued to have after the discussion phase, is the lack of theoretical guarantees (e.g., bounds on regret), which are often present in work on multi-armed bandit algorithms. However, my reading of the acceptance criteria of TMLR imply that this should not block acceptance: the paper as is has interesting and relevant contributions, describes appropriate experiments to evaluate them, and these experiments provide adequate support for the claims that are made.

There are some concerns around the extent to which the results would generalise to different datasets/problems (as there are no theoretical guarantees we can rely on), but I see quite consistent results across 5 different datasets/problems, which I view as reasonable support.

---

**I do want to request the following revisions from the authors**:
- Judging from the last paragraph of 4.3.2, on the more complex real-world task, the newly proposed algorithms use a similar amount of computation time to the baselines, not less. In light of this, the claim "our methods benefit from more effective learning with less computational overhead" could use more nuance.
- Given the prevalence of theoretical analyses in work on Multi-Armed Bandits, it would be appropriate to signal to potential readers that your evaluation of the algorithms is solely empirical. Doing this in the Introduction could be appropriate. 
- The conclusion is very short. It summarises what types of experiments were run, but does not even summarise what the outcomes were of those experiments and what conclusions follow from that. This should be added. It could also be useful to again acknowledge the limitation of the lack of theoretical results, and suggest this as a potential direction for future research.
- Try to do another round of proofreading for typos. I spotted at least one: "Asspendix" at the bottom of page 4.

Note that, for this revision, it will not be necessary to stick to 12 pages. It is fine to run a bit over this number of pages.
Decision: Accept (poster)