No-Regret Bandit Exploration based on Soft Tree Ensemble Model

Authors: shogo  iwazaki
shinya  suzumura
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 04:06:57

Abstract: We propose a novel stochastic bandit algorithm that employs reward estimates using a tree ensemble model. Specifically, our focus is on a soft tree model, a variant of the conventional decision tree that has undergone both practical and theoretical scrutiny in recent years. By deriving several non-trivial properties of soft trees, we extend the existing analytical techniques used for neural bandit algorithms to our soft tree-based algorithm. We demonstrate that our algorithm achieves a smaller cumulative regret compared to the existing ReLU-based neural bandit algorithms. We also show that this advantage comes with a trade-off: the hypothesis space of the soft tree ensemble model is more constrained than that of a ReLU-based neural network.

Main paper: 
 introduction: 
 The stochastic bandit framework is a powerful tool for addressing sequential decision-making tasks in uncertain environments. A significant challenge in applying stochastic bandits is managing large action spaces. For example, in recommendation systems, there is often a vast action space generated by various combinations of users and items [38] . Standard algorithms designed for finitearmed bandits are inadequate in these scenarios. Consequently, numerous studies have focused on structurally modeling the reward process and using limited observed data to estimate rewards for unobserved actions. These approaches include algorithms that employ estimation methods such as linear models [3, 5, 12] , kernel regression [11, 32] , and neural networks [30, 41] , which are referred to as linear bandit (LB), kernel bandit (KB), and neural bandit (NB) respectively. The effectiveness of these algorithms largely depends on the accuracy of the underlying reward models. Therefore, developing the bandit algorithms that leverage suitable reward estimation models is crucial.Motivated by these considerations, this paper explores the stochastic bandit algorithm using tree ensembles, a model type that has gained popularity following neural networks but remains relatively underexplored in the bandit context. Specifically, we focus on the soft tree ensemble model, which has recently been the subject of both practical and theoretical investigations and has demonstrated strong empirical performance on tabular data [18, 21, 22, 25, 28] . Unlike hard trees, which update decision rules greedily and sequentially, soft trees employ gradient descent to update decision rules for the entire tree. This characteristic of soft trees facilitates the extension of existing analyses of NB and ensures a no-regret performance under suitable assumptions.Related works. In the field of stochastic bandits, prior research has established various structural assumptions about underlying rewards. For instance, the assumption of Lipschitz continuity of rewards is explored in Lipschitz bandits [8] , linearity of rewards is examined in LB [3, 5, 12] , and more generally, the assumption that rewards lie in a known reproducing kernel Hilbert space (RKHS) is studied in KB [11, 32] .Our paper studies a type of bandit algorithm that employs a tree structure model, a topic with limited prior exploration. Féraud et al. [15] proposed a bandit algorithm using random forests, but the theory of their algorithm exhibits linear dependence on the number of actions, making it unsuitable for large action spaces. Elmachtoub et al. [14] introduced a Thompson sampling-style algorithm utilizing decision trees; however, their algorithm's construction relies on heuristics and does not provide a regret guarantee.Additionally, our theory is closely related to NB. Zhou et al. [41] proposed an upper confidence bound (UCB) algorithm using a deep neural net (DNN) regressor, and Zhang et al. [40] extended this analysis to Thompson sampling. Their analysis yields a regret upper bound of Õ( d√ T ), where d denotes the effective dimension of the problem, and Õ(•) represents an order notation that ignores logarithmic dependence. However, generally, DNNs employing ReLU activation functions lead to d = Õ(T (d-1)/d ), resulting in super-linear growth of O( d√ T ) regret, which becomes meaningless [23] . Several studies address this issue by employing algorithms in the form of a sup-variant of UCB [37] or phased elimination-style algorithms [7, 26] , proving a regret upper bound of Õ(T (2d-1)/(2d) ) [23, 24, 30] . These studies combine theoretical analysis via the neural tangent kernel (NTK) [4, 19] for DNN regression with regret analysis techniques from KB, constructing algorithms and performing regret analysis. Our proposed algorithm can be seen as a generalization of NB theory using a soft-tree regressor from DNN.Contributions. Our contributions are as follows:• In Sec. 3.1, we introduce a new UCB-based algorithm: soft tree-based upper confidence bound (ST-UCB), which leverages the soft tree ensemble model. This algorithm can be considered an extension of the existing NN-UCB algorithm [41] , incorporating the theory of the tree neural tangent kernel (TNTK) in soft trees [21, 22] . To our knowledge, this paper represents the first effort to extend the theory of NB to a tree-based structural model.• In Sec. 3.2, we derive several non-trivial properties of the soft tree ensemble model. These include the decay rates of eigenvalues of the TNTK (Lemma 3.1), concentration properties of TNTK (Lemma 3.2), and upper bounds on the spectral norm of the Hessian matrix (Lemma 3.3). Leveraging these results, we demonstrate that the ST-UCB algorithm achieves a regret of Õ( √ T ) under appropriate regularity conditions.• In Sec. 4 , we elucidate the distinctions in properties and assumptions between the existing NN-UCB and ST-UCB algorithms. Specifically, while NN-UCB generally lacks a no-regret guarantee in general action (or context) spaces, ST-UCB consistently offers a no-regret guarantee across general action spaces. Additionally, we examine the relation between the hypothesis spaces induced by the TNTK and those induced by the NTK using ReLU activation. This comparison reveals that the hypothesis space derived from soft trees, although more constrained, may lead to lower regret. 
preliminaries: 
 Problem setting. We consider a sequential decision-making problem whose goal is to maximize the total reward under bandit feedback. Let f : X → R be an unknown reward function, where X ⊂ R d is a finite set of action candidates. At each time step t, the environment reveals an action set X t ⊂ X ; thereafter, the learner chooses an action x t and receives the corresponding reward y t = f (x t ) + ϵ t , where ϵ t is a noise random variable whose mean is zero. As a performance metric, we adopt the pseudo cumulative regret R T := T t=1 [f (x * t ) -f (x t )], where x * t ∈ arg max x∈Xt f (x). In our problem setup, the action set X t is allowed to change at each step t. In addition to the standard bandit setup that assumes X t = X , this formulation includes a contextual bandit setup by setting X t = {(c t , a) | a ∈ A(c t )}, where c t is a context vector at step t, and A(c t ) is the corresponding action set.Soft tree ensemble. At each time step t, our algorithm constructs a soft tree-based estimator of the reward function f . We describe the definition of soft trees based on Kanoh and Sugiyama [21] . Now, let us consider M ∈ N + perfect binary trees whose depths are D ∈ N + . Note that each tree has N := 2 D -1 internal nodes and L := 2 D leaf nodes. Furthermore, for technical reasons, we assume ∈ R be the parameters of the n-th internal and l-th leaf node of the m-th tree, respectively. We index these parameters according to breadth-first ordering, as described in the left plot of Fig. 1 . Moreover, we also denote all internal and leaf node parameters as w (m) := (w(m)⊤ 1 , . . . , w (m)⊤ N ) ⊤ ∈ R N d and π (m) := (π (m) 1 , . . . , π (m) L ) ⊤ ∈ R L .The output of a standard decision tree is obtained as the parameter of some leaf node, which is chosen deterministically based on the hard-splitting rules of internal nodes. On the other hand, the output of the soft tree is given by replacing the hard-splitting operation of the standard decision tree with a probabilistic one. Specifically, given parameters θ (m) := (w (m)⊤ , π (m)⊤ ) ⊤ and any input x ∈ X , the corresponding output h(x; θ (m) ) of the m-th soft tree is defined ash(x; θ (m) ) = L l=1 π (m) l p l (x; w (m) ), where p l (x; w) = N n=1 σ(w ⊤ n x) 1l l↙n 1 -σ(w ⊤ n x) 1l n↘l .Here, 1l l↙n and 1l n↘l are indicator functions. If the l-th leaf node belongs to the left (resp. right) sub-tree whose root is the n-th internal node, 1l l↙n (resp. 1l n↘l ) is one; otherwise, zero. Furthermore, σ(•) : R → [0, 1] is a soft decision function. The right plot of Fig. 1 shows an illustrative image of the calculation of p l (•). As with [21] , we use the scaled error function σ(w ⊤ n x) := 1 2 erf(αw ⊤ n x) + 1 2 with some pre-specified scaling parameter α ≥ 0, where erf(b) = 2 √ π b 0 exp(-z 2 )dz for any b ∈ R. By aggregating M soft trees, the whole output h(x; θ) of the soft tree ensemble model is defined as h(x; θ) = M m=1 h(x; θ (m) )/ √ M , where θ := (θ (1)⊤ , . . . , θ (M )⊤ ) ⊤ ∈ R M (dN +L) . Under the model structures as described above, the training of the model parameters θ is conducted based on the gradient descent optimizer, which aims to minimize some pre-specified loss functions. In our algorithm, we adopt a regularized square loss, whose detailed definition is given in Sec. 3.1.Neural tangent kernel theory for overparameterized model. The neural tangent kernel (NTK) [19] is an effective theoretical tool for understanding the learning properties of overparameterized neural networks. Let h NN (•; θ) : R d → R be a feed-forward neural network with a ReLU activation function, L hidden layers whose width is M , and network parameters θ. Given any fixed inputs x, x ∈ R d , and θ0 ∼ N (0, I), it has been shown that the inner product ⟨∇ θ h NN (x; θ0 ), ∇ θ h NN ( x; θ0 )⟩ of gradients converges to a fixed kernel function k NTK (x, x) (i.e., ⟨∇ θ h NN (x; θ0 ), ∇ θ h NN ( x; θ0 )⟩ p -→ k NTK (x, x) as M → ∞). The kernel function k NTK is called the NTK. Moreover, in the overparameterized regime, h NN (x; θ) trained with gradient descent with an infinitesimally small learning rate coincides with the kernel ridge-less regressor h NTK (x), whose kernel function is k NTK [4] . This property motivates us to analyze NB problems by bridging original NB to KB problems whose underlying kernel function is the NTK. Indeed, some existing works [23, 24, 30, 41] show the regret upper bound of NB problems by carefully combining NTK theory with existing theoretical tools of KB. In our paper, we consider soft tree variants of these existing works.Input: X ⊂ S d-1 , D ∈ N + , J ∈ N + , η > 0, ρ > 0, α > 0, M ∈ N + , T ∈ N + , β > 0.1: Initialize θ 0 randomly as described in Sec. Obtain X t .5:Calculate σ2 t-1 (x) := g(x; θ 0 ) ⊤ I p + ρ -1 G t-1 G ⊤ t-1 -1 g(x; θ 0 ) on X t .6:x t ← arg max x∈Xt [h(x; θ t-1 ) + β σt-1 (x)].Obtain y t = f (x t ) + ϵ t .8:θ t ← TrainST(t, θ 0 , (x i , y i ) i∈[t] , J, η, ρ, D, α, m). 9: Define G t = [g(x 1 ; θ 0 ), . . . , g(x t ; θ 0 )] ∈ R p×t 10: end for Algorithm 2 TrainST (t, θ 0 , (x i , y i ) i∈[t] , J, η, D, α, M ) 1: θ t;0 ← θ 0 2: for j = 1, . . . , J do 3: Calculate gradient of L t (θ t;j-1 ) := t i=1 [h(x i ; θ t;j-1 ) -y i ] 2 + ρ∥θ t;j-1 -θ 0 ∥ 2 2 .Update parameter: θ t;j ← θ t;j-1 -η∇ θ L t (θ t;j-1 ). 5: end for 6: return θ t;J . θ ∈ R p , where p := M (dN + L) denotes the total number of parameters. Then, given fixed inputs x, x ∈ X and θ0 ∼ N (0, I p ), the inner product ⟨g(x, θ0 ), g( x, θ0 )⟩ has also been shown to converge in probability to some kernel function k TNTK (x, x) as the number of ensemble models M grows infinitely (see Theorem 1 in [21] ). This limiting kernel k TNTK is called the tree neural tangent kernel (TNTK) as an analogy to the NTK and is defined as follows:EQUATIONwhere:EQUATIONEQUATION)It should be noted that even if we follow the existing NTK-based techniques of NB, generalizing the result of Kanoh and Sugiyama [21] to the analysis of sequential decision-making tasks is non-trivial. Specifically, the existing analysis of NB heavily relies on the following results of ReLU-based NTK: i) non-asymptotic bounds of NTK [4] , ii) the spectral properties of the Hessian matrix around the initial model parameters [27] , and iii) the upper bounds of maximum information gain (MIG) of NTK [35] , which measure the complexity of the KB problem depending on the underlying kernel. These results are unique to DNN architectures with a ReLU-based activation function and are not applicable to the soft tree ensemble model.3 UCB strategy based on soft tree ensemble model 
proposed algorithm: st-ucb: 
 The pseudo-code of our proposed algorithm, soft tree-based UCB (ST-UCB), is shown in Algorithm 1. ST-UCB is interpreted as the soft tree-based variant of NN-UCB [41] . We summarize each part of ST-UCB below.Initialization. ST-UCB first chooses the initial parameter θ 0 ∈ R p for the gradient descent method as follows. Let θ base ∼ N (0, I p/2 ) be a base initial parameter, with p = M (dN + L).Using θ base , we set the initial parameters θ 0 as θ 0 = (θ ⊤ 0+ , θ ⊤ 0-) ⊤ , where θ 0+ ∈ R p/2 and θ 0-∈ R p/2 are defined as θ 0+ = (w(1)⊤ base , π (1)⊤ base , . . . , w (M/2)⊤ base , π (M/2)⊤ base ) ⊤ and θ 0-= (w (M/2+1)⊤ base , -π (M/2+1)⊤ base , . . . , w (M )⊤ base , -π (M )⊤ base ) ⊤ ,respectively. This initialization procedure ensures that the initial model output is 0 (i.e., h(x; θ 0 ) = 0 for all x ∈ X ), which is essential for our theoretical analysis.Learning. At each step t, ST-UCB learns the model parameter θ t based on a regularized squared loss L t (θ) := t i=1 (h(x i ; θ) -y i ) 2 + ρ∥θ -θ 0 ∥ 2 2, where ρ > 0 is a regularization parameter.UCB-based selection of x t . At each step t, ST-UCB selects x t as follows:EQUATIONwhereσ2 t-1 (x) = g(x; θ 0 ) ⊤ I p + ρ -1 G t-1 G ⊤ t-1 -1 g(x; θ 0 ) with g(x; θ) := ∇ θ h(x; θ) ∈ R p and G t-1 := (g(x 1 ; θ 0 ), . . . , g(x t-1 ; θ 0 )) ∈ R p×t .In ST-UCB, the quantity σ2 t-1 (x) quantifies the uncertainty of the model output h(x; θ t ) and is essential for the construction of confidence bounds. Furthermore, the quantity σ2 t-1 (x) is interpreted as the predictive variance of a Bayesian linear regression whose feature map is the gradient of the initial model output h(x; θ 0 ). We note that a similar quantity is leveraged in existing NB algorithms [23, 30, 41] .Assumptions for theoretical analysis. We make the following assumptions for our theory: Assumption 3.1. (i) The output noise ϵ t is conditionally σ-sub-Gaussian for some σ > 0. Specifically,E[exp(λϵ t ) | H t-1 ] ≤ exp(λ 2 σ 2 /2) holds for any t ∈ [T ] := {1, . . . , T } and any history H t-1 := (x 1 , y 1 , . . . , x t-1 , y t-1 ). (ii) The input space X ⊂ R d is a subset of the hyper-sphere S d-1 := {x ∈ R d | ∥x∥ 2 = 1}. (iii)The underlying reward function f is an element of the RKHS corresponding to k TNTK , where k TNTK is the TNTK induced by the same soft tree structure used in ST-UCB. (iv) The RKHS norm of f is bounded by a known constant B < ∞. That is, ∥f ∥ TNTK ≤ B holds, where ∥ • ∥ TNTK denotes the RKHS norm corresponding to k TNTK . Remark 3.1. In Assumption 3.1, (i) is the standard assumption for the stochastic bandit problem and is quite mild. For example, Bernoulli, Gaussian, and any bounded reward models are included in this assumption. Assumption (ii) is often assumed in existing NB literature [23, 24, 30, 40, 41] and holds without loss of generality by transforming the original input space through a bijection map. For example, given any original input space X ⊂ R d , we can construct a new input space X on the hyper sphereS d as X = l -1 x⊤ , (1 -∥ x∥ 2 2 l -2 ) 1/2 ⊤ | x ∈ X ⊂ S d , where l = max x∈ X ∥ x∥ 2 .Assumptions (iii) and (iv) are similar to those in existing NB works [23, 24, 30] . The only difference is that we use TNTK instead of NTK to define the hypothesis space (RKHS) to which f belongs. We omit the basic definition and properties of RKHS; see, e.g., [20] for details. In Sec. 4, we further discuss the relationship between the RKHSs corresponding to NTK and TNTK.Similar to NB with ReLU, our theoretical guarantees rely on two crucial tools in the context of KB.The first is the maximum information gain (MIG) [32] , which quantifies the complexity of the problem in the context of kernel-based sequential decision-making tasks. MIGs depend on the underlying kernels, and their upper bounds have been provided when using well-known kernels, including the NTK corresponding to NNs with ReLU [23, 35, 36] . We show the upper bound of MIG when the underlying kernel is TNTK. The second tool is the confidence bound. Constructing valid confidence bounds is crucial for obtaining meaningful regret bounds in stochastic bandit algorithms. These two elements are not only essential for the theoretical analysis of ST-UCB but also of independent interest in general sequential decision-making problems. Hereafter, we present our MIG and confidence bounds results for our ST-UCB algorithm, concluding with the regret upper bound for ST-UCB.Maximum information gain (MIG) of TNTK. Let us define the quantity γ T asEQUATIONwhere K T is the T × T kernel matrix whose (i, j)-th entry is k TNTK (x i , x j ). This γ T is called the maximum information gain (MIG) since the quantity 0.5 ln det(I T + ρ -1 K T ) is equal to the information gain from T observations in a Gaussian process regression model, characterized by the covariance function k TNTK and the noise variance parameter ρ [32] . The following Theorem 3.1 is our main result about MIG, which shows that γ T grows logarithmically. The proof of Theorem 3.1 is given in Appendix A.2. The analysis of MIG is well-studied in existing KB literature [32, 36] . The key component to quantify the upper bound of MIG is the decaying rate of the eigenvalues of the underlying kernel. The following lemma gives the decay rate of TNTK eigenvalues, which plays a central role in the proof of Theorem 3.1. EQUATIONwhere (λ n ) n∈N and (Y n,j ) n∈N,j∈[N d,n ] are eigenvalues and eigenfunctions of (the integral operator of) TNTK that satisfy λ 0 ≥ λ 1 ≥ • • • ≥ 0. In addition, for any n ∈ N, the eigenvalue λ n satisfiesEQUATIONwhere Cα,D > 0 is a constant, which depends on α and D. Remark 3.2. The eigenfunctions (Y n,j ) j∈[N d,n ] are known as spherical harmonics of degree n with multiplicity N d,n (see, e.g., [13] ). Furthermore, on the hyper-sphere S d-1 , the kernels that have rotationally invariant form can be represented in the form of Eq. (6) . TNTK and NTK with ReLU activation function are included in the rotationally invariant class of kernels; therefore, NTK can also be decomposed as Eq. (6) [35] , while corresponding eigenvalues differ from those of TNTK.The proof of Lemma 3.1 is given in Appendix A.1. Lemma 3.1 demonstrates the exponential eigenvalue decay of TNTK, in contrast to the polynomial eigenvalue decay of NTK with ReLU activation [6, 35] . This difference leads to faster convergence of ST-UCB compared to NN-UCB, albeit with a smaller corresponding RKHS of TNTK. We discuss more details in Sec. 4.The following shows the confidence bounds for the soft tree-based model. Theorem 3.2 (Confidence bounds based on the soft tree ensemble model). Suppose Assumption 3.1 holds. Fix any δ ∈ (0, 1), ρ > 0, α ≥ 1, andD ≥ 2. Let K TNTK (X ) := [k TNTK (x, x)] x, x∈X ∈ R |X |×|X |and λ 0 = λ min (K TNTK (X )) > 0 be the kernel matrix over X × X and the minimum eigenvalue of K TNTK (X ), respectively. If the number of soft tree ensemble models M is sufficiently large to satisfy M ≥ Poly(T, ρ -1 , B, α, 2 D , λ -1 0 , |X |, ln(1/δ)) and the learning rate η satisfies η ≤ O((T 2 2 4D α 2 ln(M/δ) + ρ) -1 ), then, the following event holds with probability at least 1 -δ:EQUATIONwhere:EQUATION)Remark 3.3. The minimum eigenvalue λ 0 of the kernel matrix of TNTK is guaranteed to be strictly positive if X ⊂ S d-1 . See Proposition 1 in [21] .We provide the proof of Theorem 3.2 in Appendix B.3 with the precise conditions about M and the dependence of constant factors. Our proof strategy for Theorem 3.2 follows the existing analysis of confidence bounds in NB works; however, the application of their proof techniques to the soft tree regressor is not straightforward. Specifically, the existing proof of the confidence bounds in NB depends on the concentration results of NTK (Theorem 3.1 in [4] ), and the spectral norm bounds of the Hessian matrix of NN (Theorem 3.2 in [27] ). To prove Theorem 3.2, we provide the following soft tree versions of their results.Lemma 3.2 (Concentration to TNTK). Fix any x, x ∈ S d-1 , δ ∈ (0, 1), and ϵ ∈ (0, Cα,D ) with C(2)α,D = 2 2D+2 α 2 C. If M ≥ C max{C (2)2α,D , 2 2D }ϵ -2 ln(16/δ), then,EQUATION)where θ 0 is the initial parameter of ST-UCB, and C, C > 0 are absolute constants.Lemma 3.3 (Spectral norm upper bound). For any δ ∈ (0, 1) and α ≥ 1, with probability at least 1 -δ, the following holds for any R > 0, θ ∈ R p , and x ∈ S d-1 :EQUATIONwhere H(x, θ) := ∇ 2 θ h(x; θ) ∈ R p×p is the Hessian matrix of the model output, and Cα,D = √ 6α 2 2 2D . Furthermore, for any A ∈ R p×p , ∥A∥ := max z∈S p-1 ∥Az∥ 2 denotes the spectral norm.The proofs of Lemma 3. Regret upper bound of ST-UCB. By combining Theorem 3.1 and Theorem 3.2 with the standard proof technique of the kernelized UCB algorithm, we obtain the Õ( √ T ) regret upper bound for ST-UCB as stated in the following theorem. The proof is provided in Appendix C. Theorem 3.3. Suppose that Assumption 3.1 holds. Fix any δ ∈ (0, 1), α ≥ 1, ρ > 0, and D ≥ 2. Furthermore, assume that the confidence width parameter β satisfies Eq. (9) . If the number of soft tree ensemble models M and the total step size J of the gradient descent are sufficiently large to satisfy M ≥ Poly(T, ρ -1 , B, α, 2 D , λ -1 0 , |X |, ln(1/δ)), and the learning rate η satisfies η ≤ O((T 2 2 4D α 2 ln(M/δ) + ρ) -1 ), then, the following holds with probability at least 1 -δ:EQUATION)4 Comparison of NN-UCB and ST-UCB Comparison of regret. In the existing NN-UCB algorithm [41] , a regret upper bound of O( d√ T ) is provided, where d represents the effective dimension of ReLU-based NTK. It is generally known that the worst-case bound of the effective dimension and MIG are equivalent up to logarithmic dependencies [37] . Considering the upper bound on MIG of NTK, γ [23, 35] , the regret of NN-UCB becomes Õ(T (d-1)/d+1/2 )(= Õ(γ(NTK) T = Õ(T (d-1)/d )(NTK) T √ T )).This results in a superlinear regret, and meaningful guarantees for NN-UCB are not achievable without further restricted assumptions on the input set X t (e.g., see the discussion in Appendix D in [40] ). To address these issues in a general setting, it is necessary to construct more complex algorithms that incorporate concepts such as a sup-variant of UCB [23, 30] or phased elimination [24] , yielding a regret upper bound of O( γ (NTK) T T ). In contrast, due to Theorem 3.1, the MIG of TNTK γ (TNTK) T diverges on a logarithmic scale. Therefore, ST-UCB achieves a regret bound of Õ( √ T ) without requiring additional assumptions on the input set X t , maintaining a simple UCB-style algorithmic structure.Comparison of hypothesis space. In our analysis, we assume in Assumption 3.1 that the reward function f belongs to the RKHS H TNTK associated with TNTK. Conversely, in existing NB research, it is assumed that f belongs to the RKHS H NTK associated with NTK. By combining Lemma 3.1 with the well-known Mercer's representation theorem (e.g., Theorem 4.51 in [33] ), we derive the following lemma, which describes the relationship between H TNTK and H NTK . Lemma 4.1. Fix any α ≥ 0 and D ∈ N + , and define the corresponding TNTK as k TNTK : The proof of Lemma 4.1 is provided in Appendix D. Lemma 4.1 indicates that the regret upper bound of ST-UCB is guaranteed in a more constrained hypothesis space compared to NN-UCB. While NN-UCB generally does not guarantee a no-regret property, the Õ( √ T ) guarantee in ST-UCB can be interpreted as being due to focusing on a more constrained hypothesis space.S d-1 × S d-1 → R. Let k NTK : S d-1 × S d-1 → RIt should be noted that whether this property is specific to the tree structure of the model or depends on the choice of the soft-decision function is unknown. We constructed and analyzed our algorithm based on the definition of soft trees from [21] ; however, we conjecture that by using a more non-smooth soft decision function, although the regret may degrade to a level similar to NN-UCB, we can align the hypothesis spaces used in NN-UCB and ST-UCB to be almost the same. We leave the detailed analysis to future work.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [No] Justification: We are not yet ready to release the required codes and will do so as soon as our paper is accepted. Furthermore, we believe that the lack of experimental codes is not problematic because our experiment are not too complex, and the information given in Sec. 5 and Appendix F. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: There is no societal impact of the work performed. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
numerical experiments: 
 In this section, we compare ST-UCB and NN-UCB to empirically demonstrate the usefulness of the tree-based model. Additionally, to evaluate the characteristics of UCB-based algorithms, we include ϵ-greedy based ST-greedy and NN-greedy as comparative methods.Real-world dataset. We use Energy Efficiency dataset [34] registered in UCI Machine Learning Repository [1] . This dataset provides the load required to maintain comfortable indoor air conditions for each of the 768 residential buildings -two types of data are provided as non-negative real values: heating load (HL) and cooling load (CL). For each building, eight types of context are included as explanatory variables. We randomly sample residential buildings without replacement to create a dataset of K ≤ 768 arms, where K is a hyperparameter. The inputs are denoted as x = ( xbuilding , x) ∈ X , where xbuilding is a K-dimensional one-hot vector used to identify the arms, and x is a vector that aggregates the eight types of context. In most real-world data, the rewards depend not only on the observable context x but also on other information. To account for arm-specific characteristics that cannot be represented by x alone, we use xbuilding as part of the input.We consider each arm of the multi-armed bandit problem as an individual residential building, and we define the reward of the arm selected in each round as f t = -(HL t + CL t ). Additionally, we standardize the rewards across K arms to have a mean of 0 and a standard deviation of 1.Synthetic dataset. We evaluate the algorithms using synthetic data similar to that used in [41] .Here, the number of arms is set to 20, and the dimension of the input vector x for each arm is set to 50. Additionally, the input vectors are chosen uniformly at random from the unit ball. We consider the three reward functions: (i) f (1) (x) = 10(x ⊤ a) 2 , (ii) f (2) (x) = x ⊤ A ⊤ Ax, and (iii) f (3) (x) = cos(3x ⊤ a)where a ∈ R 50 is randomly generated from uniform distribution over unit ball, and each entry of A ∈ R 50×50 is randomly generated from standard normal distribution. Similar to the real-world dataset, we standardize the rewards across all arms.Setup. We define the cumulative regret up to round T as R T = T t=1 f * -f t where f * represents the maximum reward among all arms. We assume that the response used for training the machine learning model is generated from y t = f t + ϵ t where ϵ t is randomly drawn from a normal distribution with mean 0 and standard deviation σ noise = 0.2. Since the rewards are standardized, this setting of σ noise effectively acts as noise.In this experiment, we will use an ϵ-greedy based algorithm as an additional comparative method; In each round, an arm is selected randomly with a probability of ϵ, while the arm with the highest f (1) (x) = 10(x ⊤ a) 2 f (2) (x) = x ⊤ A ⊤ Ax f (3) (x) = cos(3x ⊤ a)Figure 2 : The average cumulative regret with one standard error. The experiment was conducted over 10 episodes with different initial parameters for the model.predicted value from the machine learning model is selected with a probability of 1 -ϵ. Here, we will perform a grid search to choose the value of ϵ from the three candidates ϵ ∈ {0.05, 0.1, 0.2}. Meanwhile, in UCB-based algorithms, β is provided as a parameter to control the degree of exploration.We use a grid search to select the value of β from the three candidates β ∈ {0.01, 0.1, 1}.We employ a fully connected neural network model with two intermediate layers. Including the input and output layers, the total number of layers is four. Each of the two intermediate layers contains 33 units, one of which is a bias term. As for the tree-based model, we consider an ensemble of four soft-trees, the depth of each soft-tree is three. The regularization coefficient λ for the parameters is fixed at 10 -4 , regardless of the machine learning model. Supplementary details related to the implementation of the algorithms are summarized in Appendix F.1.Results. The results for each algorithm are shown in Fig. 2 . In real-world dataset, three different numbers of arms were considered, with K being one of {20, 40, 60}. These experiments were conducted over 10 episodes with different initial parameters θ 0 for the model. Additional results without the grid search for ϵ, β are summarized in Appendix F.2.In all settings of real-world dataset, the regret of ST-UCB was not smaller in the early rounds, but the increase in the cumulative regret became more gradual as the rounds progressed. For example, in the setting of K = 60, after round 150, there was no change in the cumulative regret of ST-UCB. However, from round 1 to 70, the regret of ST-UCB was relatively high compared to other methods.In our experiment, UCB-based policies (NN-UCB, ST-UCB) tended to actively select arms that had not been chosen before in the early rounds. As the rounds increased, exploratory behavior was suppressed, and there was a stronger tendency to select only arms with high rewards. On the other hand, in policies based on ϵ-greedy (NN-greedy, ST-greedy), the exploration rate is kept at ϵ across all rounds. Therefore, the regret continues to accumulate gradually as the rounds increase, raising concerns about worsening cumulative regret over extended long rounds. In the f (1) and f (2) settings of synthetic dataset, ST-UCB outperformed the other policies, and the convergence stability of cumulative regret in f (3) was comparable between ST-UCB and NN-UCB. 
conclusion and future direction: 
 In this paper, we propose a new regret-minimization algorithm based on a soft tree ensemble model. Our analysis extends the theoretical framework of existing neural bandit (NB) approaches to the soft tree ensemble model, demonstrating, under appropriate assumptions, the achievement of Õ( √ T ) regret. To our knowledge, this is the first application of NB theory to models other than neural networks; we believe that our work marks an important first step toward developing exploration and exploitation theory using various complex models beyond neural nets.Our future research directions are outlined below. Firstly, it is important to study the extension when employing hard decision trees. In this paper, as the scale parameter α approaches infinity, the soft tree regressor approaches that of a hard tree. We conjecture that our algorithm also works in this regime; however, since our regret analysis assumes a fixed α, our proposed method is not guaranteed to maintain the no-regret property with a varying scale parameter α. Hence, a more careful theoretical treatment is needed for this extension. Secondly, we plan to generalize the theory to encompass more common learning methods of the ensemble tree model. Specifically, learning algorithms using hard trees often utilize optimization methods in a greedy format rather than gradient descent. Therefore, developing theoretical foundations for ensemble tree learning methods that are more practically applicable is crucial. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: Our paper cited the original papers to use UCI-Machine Learning Repository in Sec. 5.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: Our paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: Our paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: Our paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A.1 Proof of Lemma 3.1 Firstly, we formally define the dot product kernel on the sphere. Definition A.1 (Dot product kernel on the sphere [31] ). Let d ≥ 2 and S d-1 be the unit sphere of R d . Then, a kernel k : S d-1 × S d-1 → R of the following form is called a dot product kernel on the sphere S d-1 :EQUATIONwhere (b n ) n∈N is an absolutely summable sequence. Furthermore, if b n ≥ 0 for any n ∈ N, k is a continuous positive semi-definite kernel on the sphere S d-1 .As described in Sec. 2 in [31] , continuous positive semi-definite dot-product kernels are decomposed as Eq. ( 6) by using spherical harmonics (Y n,j ).The following lemma shows the eigendecay of dot product kernels depending on coefficients(b n ) n∈N . Lemma A.1 (Proposition 2.3 in [31]). Let d ≥ 2 and (Y n,j ) j∈[N d,n ] be the spherical harmonics of degree n. Furthermore, let k(x, x) := ∞ n=1 b n (x ⊤ x) n be a continuous positive semi-definite dot-product kernel on S d-1 . Here, if there exist r ∈ (0, 1) and c > 0 such that b n ≤ cr n holds for any n ∈ N, then, there exists constant C > 0 and(λ n ) n∈N such that λ n ≤ Cr n and k(x, x) = ∞ n=0 N d,n j=1 λ n Y n,j (x)Y n,j ( x) hold for all x, x ∈ S d-1, and n ∈ N.To prove Lemma 3.1, we consider the Maclaurin series expansion of TNTK; then, Lemma 3.1 is given from Lemma A.1.Proof of Lemma 3.1. First, we respectively define functionsEQUATIONEQUATION)Then, since x, x ∈ S d-1 , the following holds directly from the analytical expression of TNTK [21] :EQUATIONHere, sinceEQUATIONfrom the Maclaurin series expansion of the inverse sine function. Furthermore, since -1 <EQUATIONwhere the last line follows from the fact that(1 + x) c = ∞ n=0 c nx n holds for any c ∈ R andx ∈ (-1, 1). Here, c n denotes a generalized binomial coefficient, which is defined asc n = 1 if n = 0; otherwise, c n = c(c-1)•••(c-n+1) n!. By rearranging Eq. ( 18) and Eq. ( 21), f 1 and f 2 can respectively be rewritten asEQUATIONi a i , where the coefficients bEQUATIONEQUATION)From the Stirling's inequality: e(n/e) n ≤ n! ≤ en(n/e) n , for any i such that i = 2n + 1 holds,EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONTherefore, 0 ≤ b(1) i ≤ e -1α 2 α 2 +0.5 i holds for any i ∈ N. Furthermore, for any i such that i = 2n holds,EQUATIONEQUATIONEQUATION) Therefore, 0 ≤ b (2) i ≤ α 2 π(1+2α 2 ) α 2 α 2 +0.5i holds for any i ∈ N. Now, we rewrite Eq. ( 16) by using the multiple Cauchy product formula as follows:EQUATIONwhere,EQUATIONBy combining Eq. ( 34) with the upper bounds of bi and bEQUATION)Therefore, there exist constant Cα,D > 0 such thatb i ≤ Cα,D α 2 α 2 + 0.25 iD (38)holds for any i ∈ N. By applying Lemma A.1 with Eq. ( 38), we haveEQUATION= C(1)EQUATIONfor some constant Cα,D > 0.A.2 Proof of Theorem 3.1Our proof strategy of Theorem 3.1 is adapted from [23, 35] .Proof of Theorem 3.1. Fix any deterministic sequence x 1 , . . . , x t ∈ X ⊂ S d-1 . For any M ∈ N+, let us define kernel functions k(M )TNTK and k(M) TNTK asEQUATIONEQUATIONFurthermore, letK (M )TNTK and K(M) TNTK be t × t-kernel matrices whose (i, j)-th entry are k(M )TNTK (x i , x j ) and k(M) TNTK (x i , x j ), respectively. As with the proof of Theorem 3 in [36] , we have the following decomposition:EQUATIONBy following the same argument as the proof of Theorem 2 in [35] , the first term of Eq. ( 44) is bounded from above as follows:EQUATION)whereN M = M n=1 N d,n and k = max x∈X k TNTK (x, x). Furthermore, by following the same argument as the proof of Theorem 3.2 in [23] , the second term of Eq. ( 44) is bounded from above as follows:EQUATIONEQUATIONThen, from Lemma 3.1, there exists some constants C > 0 andEQUATIONwhere we set C α as C α = ln(1 + 1/(4α 2 )). Furthermore, Eq. (50) follows from N d,n = Θ(n d-2 ) (see, e.g., [23] ). Therefore,EQUATIONwhere we set Cα,D,d as Cα,D,d = C(1)EQUATIONEQUATION)By choosing M asEQUATIONM ≥ 1 for sufficiently large t, and we haveEQUATION)Therefore,EQUATIONThe above inequality holds for any choice of x 1 , . . . , x t ; hence, the proof is completed.To prevent the subscript from becoming redundant hereafter, unless specifically stated otherwise, we denote the initial parameter θ 0 by θ := θ 0 , and the initial parameters of the m-th tree are denoted by θ (m) . Moreover, the initial parameter vectors corresponding to the internal nodes and leaf nodes for θ (m) are denoted by w (m) and π (m) , respectively. First, following [21] , we decompose the finite sample approximation of the TNTK as follows:EQUATION)Here, w (m),(T ) , w (m),(L) , and w (m),(R) represent the parameters of the root (top) node, all internal nodes of the left subtree, and all internal nodes of the right subtree of the m-th tree at the initial values, respectively. Now, we define k(T ) TNTK (x, x), k (L) TNTK (x, x), k (R)TNTK (x, x), and k (B) TNTK (x, x) as follows:EQUATIONEQUATIONEQUATIONEQUATION)Note that, since the initial parameters of each tree follow the same distribution, the definitions mentioned above do not depend on the choice of m. Now, assuming that the initial parameters follow a multivariate normal distribution independent across dimensions, by using the law of large numbers, Eqs. ( 68), (69), and (70) converge in probability, respectively, to k(T ) TNTK (x, x), k (L) TNTK (x, x) + k (R) TNTK (x, x), and k (B) TNTK (x, x). From the continuous mapping theorem, it fol- lows that k TNTK (x, x) = k (T ) TNTK (x, x) + k (L) TNTK (x, x) + k (R) TNTK (x, x) + k (B)TNTK (x, x) can be expressed [21] . Note that the convergence to the above TNTK also holds for the initialization strategy of ST-UCB. Actually, regarding Eq. (68), we haveEQUATIONThe first and second terms correspond to the inner products of gradients when initializing M/2 soft trees with the standard normal distribution and converge in probability to k (T ) TNTK (x, x). Therefore, by the continuous mapping theorem, Eq. (75) converges in probability to k (T ) TNTK (x, x). Similar arguments apply to k(L) TNTK (x, x) + k (R) TNTK (x, x) and k (B)TNTK (x, x), indicating that in the initialization strategy of ST-UCB, ⟨∇ θ0 h(x; θ 0 ), ∇ θ0 h ( x; θ 0 )⟩ also converges in probability to k TNTK (x, x). The following three lemmas each evaluate the concentration to k EQUATIONwhere K = 4α 2 CL 2 . Furthermore, C, c > 0 are absolute constants.Lemma B.2. For any x, x ∈ S d-1 , ϵ ≥ 0, and D ≥ 2, we haveP k (L) TNTK (x, x) - 1 M M m=1 ∇ w (m),(L) h (m) x; θ (m) 0 , ∇ w (m),(L) h (m) x; θ (m) 0 ≤ ϵ ≥ 1 -4 exp -c min ϵ 2 K 2 , ϵ K M .(78)Furthermore, we haveEQUATION)Lemma B.3. For any x, x ∈ S d-1 and ϵ ≥ 0, we haveEQUATION)Here, c > 0 is an absolute constant.In proving the above lemmas, following [21] , we denote a single soft tree of depth D determined by the internal node parameters w ∈ R d(2 D -1) and leaf node parametersπ ∈ R 2 D as h D (•, w, π). Proof of Lemma B.1. Fix any D ≤ D, w ∈ R d(2 D -1), and π ∈ R 2 D . From the definition of the soft tree, the following recursive formula holds [21] :EQUATIONNote that h (m) (x; θ (m) ) = h D x, w (m) , π (m) . Here, π (L) , π (R) represent the parameters of the leaves belonging to the left and right subtrees, respectively. From Eq. (81), we haveEQUATIONwhere σ(bEQUATIONHere, let us define p D,l (x, w):= 2 D -1 n=1 σ w ⊤ n x 1l l↙n 1 -σ w ⊤ n x1l l↘n as the weight probability function of leaf l in a soft tree of depth D; then, we haveEQUATION)Since the sub-Gaussian norm of the normal distribution is bounded from above by a constant multiple of its standard deviation (see, e.g., Example 2.5.6 in [39] ), for any m ∈ [M ], we haveEQUATIONwhere the first inequality follows from p D-1,l x, w (m),(L) ≤ 1. Similarly,EQUATION) Due to ∥ σ(•)∥ ∞ ≤ α/ √ π, x ⊤ x ≤ 1,and Lemma E.4, we obtainEQUATION)From the centering lemma (Lemma E.3), there exists an absolute constant C > 0 such thatEQUATIONTherefore, taking CC 2 as a new absolute constant C and using the independence of parameters for each m ∈ [M/2], the application of Bernstein's inequality (Lemma E.2) yieldsEQUATIONNote that the similar inequality also holds for m ∈ [M ] \ [M/2]:EQUATION)By taking union bound in Eqs. ( 92) and (93) and taking c/2 as an new absolute constant c , we obtain the desired result.Proof of Lemma B.2. We only show Eq. (78) for simplicity. Fix any w ∈ R dN and π ∈ R L corresponding to the parameters of a soft tree of depth D. Furthermore, let w i: and π i: (1 ≤ i ≤ N ) represent the internal node parameter vectors and the leaf node parameter vectors, respectively, for the subtree rooted at the i-th internal node (note that the parameter indices are assigned in breadth-first order, hence by definition, w 2: = w (L) , w 3: = w (R) ). From Eq. (81), we have:EQUATION)Given that ∥σ(•)∥ ∞ ≤ 1, for any m ∈ [M ], we have:EQUATIONNow, decomposing the gradient of the subtree rooted at the left child of the root node, we have:EQUATION)Considering that w 2: are parameters for a soft tree with L/2 leaves, similar to the proof of Lemma B.1, there exists an absolute constant C such that for any m ∈ [M ]:EQUATION, ∇ w (m),(T ) 2:EQUATIONEQUATIONSimilarly to Eq. ( 95), we have:EQUATION2: , π, ∇ w (m),(L) 2: , πEQUATIONEQUATION)Similarly, for the right subtree:EQUATION, ∇ w (m),(R)EQUATION, π(m),(R) 2: , ∇ w (m),(R) 2: h D-2 x, w (m),(R) 2:, πEQUATIONTherefore,∇ w (m),(L) h D-1 x, w (m),(L) , π (m),(L) , ∇ w (m),(L) h D-1 x, w (m),(L) , π (m),(L) ψ1 ≤ 4α 2 Cπ -1 (L/2) 2 + ∇ w (m),(L) 2: h D-2 x, w (m),(L) 2:, π (m),(L) 2:, ∇ w (m),(L) 2:h D-2 x, w (m),(L) 2:, π (m),(L) 2: ψ1+ ∇ w (m),(R) 2: h D-2 x, w (m),(R) 2:, π(m),(R) 2:, ∇ w (m),(R)2: h D-2 x, w (m),(R) 2:, πEQUATION)By repeating the above described argument, we can further decompose the second and third term of Eq. (102) as follows:EQUATIONEQUATION, ∇ w (m) 8:EQUATION(106)EQUATION, ∇ w (m) 9:EQUATION(107)+ ∇ w (m)10:EQUATION, ∇ w (m) 10:EQUATION10: , π (m) 10: ψ1(108)+ ∇ w (m)11:EQUATION11: , π, ∇ w (m)11:EQUATION)By recursively applying the above discussion until reaching the leaves of the tree, we find:∇ w (m),(L) h D-1 x, w (m),(L) , π (m),(L) , ∇ w (m),(L) h D-1 x, w (m),(L) , π (m),(L) ψ1 ≤ 4α 2 Cπ -1 L 2 2 + 2 × 4α 2 Cπ -1 L 4 2 + • • • + 2 D-2 × 4α 2 Cπ -1 L 2 D-1 2 .(110) Thus, we conclude:EQUATIONEQUATIONFinally, by applying centering lemma (Lemma E.3), Bernstein's inequality (Lemma E.2), and the union bound, we obtain the desired result.Proof of Lemma B.3. From the definition of h (m) , we have:EQUATION)Noting that |p l (x; w)| ≤ 1, we have:EQUATIONTherefore, by applying the centering lemma (Lemma E.3) and the general Hoeffding's inequality (Lemma E.1) with union bounds, the desired result is obtained.Lemma 3.2 is derived by taking a union bound over the three preceding lemmas and rearranging the entire expression.Proof of Lemma 3.2. Fix any ϵ > 0 such that ϵ ≤ K. Then,EQUATIONEQUATIONTherefore, from Lemma B.1, Lemma B.2, and Lemma B.3, by applying the union bound,EQUATIONEQUATIONFinally, let C = max{1/c, 1/c}, thenEQUATION)By defining C(2)EQUATIONα,D = K, the desired result is obtained.Proof scketch Since the parameters of the different soft trees are independent, we can confirm that the Hessian H(x, θ) is given as the block diagonal matrix. Since we know the fact that the spectral norm of the block diagonal matrix equals the maximum over the spectral norms of the block matrix, the remaining interest is the upper bound of the spectral norm of each block matrix. Then, we obtain Lemma 3.3 by carefully evaluating the upper bound of the spectral norm of each block matrix with its Frobenius norm. m) x; θ (m) ∈ R p× p, where p = dN + L. Then, H(x, θ) is represented by the following block diagonal matrix:Proof of Lemma 3.3. Define H (m) x, θ (m) = ∇ 2 θ (m) h (H(x, θ) = 1 √ M     H (1) x, θ (1) 0 p× p . . . 0 p× p 0 p× p H (2) x, θ (2) . . . 0 p× p . . . . . . . . . . . .EQUATION)where 0 p× p represents a p × p zero matrix. Therefore,EQUATIONHere, assume the following event holds:EQUATIONSince θ 0 is initialized by a standard normal distribution, by the union bound, the above event occurs with probability at least 1 -δ. Therefore, it is sufficient to show that Eq. ( 11) holds under the event (128). Now, the derivatives of h (m) (x; θ (m) ) up to the second order are given by:EQUATIONEQUATIONEQUATIONFrom the definition of p l , we haveEQUATIONEQUATIONEQUATIONIn the third equation, it was assumed that n ̸ = n. Now, let us evaluate the upper bound of the above expressions. First, from the definition of σ(•), we know that ∥σ(•)∥ ∞ ≤ 1 and ∥ σ(•)∥ ∞ ≤ α/ √ π. Additionally, for any a ∈ R, |σ(a)| ≤ 2|a|α 2 / √ π. Then, ∂ 2 p l x; w (m) ∂w (m) n ∂w (m) n F ≤ σ w (m)⊤ n x 1l l↙n xx ⊤ -1l n↘l xx ⊤ F (135) ≤ 2 w (m)⊤ n x α 2 √ π xx ⊤ F (136) ≤ 2 w (m)⊤ n x -w (m)⊤ n x + w (m)⊤ n x α 2 √ π ∥x∥ 2 2(137)EQUATIONFurthermore, as for n ̸ = n,EQUATIONMoreover, we haveEQUATIONTherefore,EQUATIONwhere:• Eq. ( 150) follows from Eq. (131).• Eq. ( 151) follows from Eqs. ( 146) and (130).• The first and second term of Eq. ( 152) follows from Eq. ( 143) and Eq. ( 138), respectively. Furthermore, the third term of Eq. ( 152) follows from ∂p l (x;w (j) )∂w (j) n F ≤ 1l l↙n x σ w (j)⊤ n x -1l n↘l x σ w (j)⊤ n x F ≤ ∥ σ(•)∥ ∞ ≤ α √ π .• Eq. ( 154) follows from 1/π ≤ 1 and α ≥ 1.• Eq. ( 155) follows from R + 2 ln 2M (L+N )δ 4 ≥ ( √ 2 ln 2) 4 ≥ 1.By combining Eq. ( 155) with Eq. ( 127), we haveEQUATION)Finally, from the definition of C(3)EQUATIONEQUATIONwhere Eq. (159) follows from ln(2M (N + L)/δ) ≥ ln 6 ≥ 1. Furthermore, Eq. (161) follows from L + N ≤ 2 D+1 . By combining Eq. (161) with Eq. (157), we obtain the desired result.Instead of showing Theorem 3.2 directly, we show the proof of the following detailed version of Theorem 3.2.Theorem B.1 (Detailed version of Theorem 3.2). Suppose that Assumption 3.1 holds. Fix any δ ∈ (0, 1), α ≥ 1, ρ > 0, and D ≥ 2. Furthermore, suppose that the number of ensemble M is sufficiently large to satisfy the following four conditions:EQUATIONEQUATIONEQUATIONEQUATIONwhere:EQUATIONEQUATION)Then, if the learning rate η satisfy η ≤ 4-1 ρ + 2(2 R + 2 D Ĉ) 2 T C (4) α,D ln 6M δ -1, with probability at least 1 -δ, the following inequality holds for any t ∈ [T ] and x ∈ X :EQUATIONwhere:EQUATIONHere, C > 0 and Ĉ > 0 are absolute constants. Furthermore, Cα,D > 0, Cα,D > 0, and Cα,D > 0 are constants that depend on α and D. Moreover, k := max x∈X k TNTK (x, x) is the square root of the maximum value of TNTK, and C (7) α,D,T = O(T 3 ) is the constant that depends on α, D, and T .In this section, we briefly summarize the overview of our proof. We first define the following six events:EQUATION.• E 6 = ∀t ∈ N + , ∀x ∈ X , |f (x) -μt-1 (x)| ≤ √ 2B + σ √ ρ 2(γ t + ln 6 δ ) σt-1 (x) .The quantities k, Cα,D , Cα,D , Cα,D , μt-1 , k, and γt are defined in Lemma B.4-B.7. Only the above six events require probabilistic arguments in our proof. Actually, from Lemma 3.3 and Lemma B.4-B.7, which we will show later, we can confirm the events E 1 , . . . , E 6 simultaneously holds with probability at least 1 -δ for sufficiently large M by taking union bound; therefore, it is enough to show Eq. (168) under the event i∈ [6] E i . Hereafter, we show Theorem B.1 in the following steps:1. For sufficiently large M , we show that each of the events E 2 ∩ E 3 , E 4 , and E 5 holds with probability at least 1 -δ/6 in Lemma B.4, Lemma B.5, and Lemma B.6, respectively. Furthermore, as shown in Lemma B.7, the event E 6 holds with probability at least 1 -δ/3. Since we already know the event E 1 holds with probability at least 1 -δ/6 from Lemma 3.3, we can show P i∈ [6] E i ≥ 1 -δ in this step by applying the union bound.2. As with the proof of Salgia [30] , the error term |f (x) -h(x; θ t )| is decomposed as follows:EQUATIONBased on the above decomposition, we derive the upper bound of each term under the event i∈ [6] E i with sufficiently large M . The first term of the above inequality is bounded from above by combining the event E 6 with Lemma B.12. The second term is bounded by resorting to the arguments from [41] , which is based on the optimization error of the gradient descent of the linearized squared loss (Lemma B.9 and Lemma B.11). The upper bound of the third term is obtained by combining the event E 1 with the fact that the error of the first-order Taylor approximation can be characterized by the spectral norm of the Hessian.Lemma B.4 (Gradient norm bounds). Let δ ∈ (0, 1), M ≥ 3, and α ≥ 1. Furthermore, let θ 0 be an initial parameter of ST-UCB. Then, with probability at least 1 -δ, for any x ∈ S d-1 , R ≥ 0, andEQUATIONEQUATION)where Ĉ > 0 is an absolute constant. Moreover, Cα,D = 2 D+2 α 2 and C(5)α,D = 7 • 2 3D Ĉα 2 .Proof. Suppose there exists u ≥ 1 such that the following event holds:EQUATION)Following the proof of Lemma 8 in [21] , we can derive that:EQUATIONEQUATION)Furthermore, in the second inequality, we obtain the following upper bound from the Schwarz's inequality:1 M M m=1 N n=1 α L l=1 |π (m) l -π (m) l | + 2αu N ñ=1 ∥w (m) ñ -w (m) ñ ∥ 2 2 (178) + L l=1 N n=1 ∥w (m) n -w (m) n ∥ 2 2 (179) ≤ 1 M M m=1 N n=1 2α 2 L∥π (m) -π (m) ∥ 2 2 + 4α 2 u 2 N 2 ∥w (m) n -w (m) n ∥ 2 2 (180) + L l=1 N ∥w (m) n -w (m) n ∥ 2 2 (181) ≤ 1 M M m=1 N 2α 2 L + 4α 2 u 2 N + L ∥θ (m) -θ (m) ∥ 2 2 (182) = N 2α 2 L + 4α 2 u 2 N + L M ∥θ -θ∥ 2 2 (183) ≤ 7α 2 N Lu 2 M R 2 (184)Here, using the general Hoeffding's inequality (Lemma E.1) and the union bound, the event (173)holds with probability at least 1 -δ when u = ĈL ln(M/δ), where Ĉ ≥ 1 is an absolute constant.Therefore, with probability at least 1 -δ:EQUATION)Finally, from the definition of Cα,D ,EQUATIONwhere:• Eq. ( 188) follows from (2R + L Ĉ) 2 α 2 ≥ L since α ≥ 1, Ĉ ≥ 1, and R ≥ 0.• Eq. ( 189) follows from N ≤ 2 D and L Ĉ ≥ 1.• Eq. ( 190) follows from √ ln 2 ≥ ln 2 ≥ 0.5.• Eq. ( 191) follows from the fact that ln(M/δ) ≥ ln 2 holds under M ≥ 2.Lemma B.5. Fix any δ ∈ (0, 1) and f ∈ H TNTK with ∥f ∥ TNTK ≤ B. Furthermore, suppose that ϵ t is a σ-sub-Gauss random variable for any t ∈ [T ]. Then, with probability at least 1 -δ, the following inequality holds for any t ∈ [T ]:EQUATIONwhere k = max x∈X k TNTK (x, x).Proof. From the reproducing property of RKHS and Schwarz's inequality, for any x ∈ X , we haveEQUATION)Thus,EQUATIONEQUATION)By using the concentration property of σ-sub-Gauss random variable, for any t ∈ [T ] and δ ∈ (0, 1),EQUATION)By setting δ as δ = δ/T and taking the union bound, we complete the proof.Lemma B.6. Let δ ∈ (0, 1), D ≥ 2, and X ⊂ S d-1 . Furthermore, let K TNTK (X ) := [k TNTK (x, x)] x, x∈X ∈ R |X |×|X | and λ 0 = λ min (K TNTK (X )) > 0 be kernel matrix over X × X and the minimum eigenvalue of K TNTK (X ), respectively. Moreover, assume thatM ≥ 64C (6) α,D |X | 2 λ -2 0 ln 16|X | 2 δ and M ≥ C (6) α,D C (2)-2 α,D ln 16|X | 2 δ (201)hold, whereC (6) α,D = C max{C (2)2 α,D , 2 2D }.Here, C and C(2)α,D are defined in Lemma 3.2. Then, with probability at least 1 -δ, the following inequality holds for any x, x ∈ X :EQUATIONEQUATIONEQUATION)where k(x, x) = ⟨g(x; θ 0 ), g( x; θ 0 )⟩.Proof. From Lemma 3.2 and the union bound, for any ε ∈ (0, Cα,D ), we haveM ≥ C (6) α,D ε -2 ln 16|X | 2 δ ⇒ P(∀x, x ∈ X , |k TNTK (x, x) -⟨g(x, θ 0 ), g( x, θ 0 )⟩| ≤ 4ε) ≥ 1 -δ. (203)Here, we set ε as εEQUATIONα,D ). Therefore, by using Eq. ( 203), we haveEQUATIONEQUATIONEQUATION)Furthermore,EQUATION)By combining the above implication with Eq. ( 203), we complete the proof.Lemma B.7. Fix any δ ∈ (0, 1) and f ∈ H TNTK with ∥f ∥ TNTK ≤ B. Let us define k as k(x, x) = ⟨g(x; θ 0 ), g( x; θ 0 )⟩. Furthermore, suppose that (ϵ t ) t∈N+ are conditionally σ-sub-Gaussian random variables. Then, under the event E 5 , with probability at least 1 -δ,EQUATIONHere, we respectively define μt-1 (x) and γt asEQUATIONEQUATION)where kt (x) = [ k(x, x i )] i∈[t] ∈ R t and Kt = [ k(x i , x j )] i,j∈[t] ∈ R t×t with k(x, x) = ⟨g(x; θ 0 ), g( x; θ 0 )⟩.Proof. From the definition of E 5 , we have|k TNTK (x, x) -⟨g(x, θ 0 ), g( x, θ 0 )⟩| ≤ λ 0 /(2|X |) for any x, x ∈ X . Therefore, x, x∈X |k TNTK (x, x) -⟨g(x, θ 0 ), g( x, θ 0 )⟩| 2 ≤ λ 0 /2.Here, by combining this inequality with the arguments of the proof of Lemma C.5 in [24] , under the event E 5 , we have f ∈ H k with ∥f ∥ k ≤ √ 2B. Therefore, since μt and σt are defined as the posterior mean and the posterior variance of Gaussian process characterized by the kernel function k, we obtain the desired result by applying Lemma 3.11 in [2] .Lemma B.8. Fix any δ ∈ (0, 1); then, P(∩ i∈ [6] E i ) ≥ 1 -δ holds.Proof. From Lemma 3.3, B.5, and B.6, we have P(E c i ) ≤ δ/6 for any i ∈ [5]/{2, 3}. In addition, from Lemma B.4, we have P(E c 2 ∪ E c 3 ) ≤ δ/6. Here, from Lemma B.6 and Lemma B.7, we haveEQUATIONEQUATION)Therefore, by taking the union bound, we have EQUATIONEQUATION)Furthermore, let us define θt;1 , . . . , θt;J asEQUATION)where θt;0 = θ 0 . Lemma B.9 (Adapted from Lemma C.4 in [41] ). Suppose that the events E 2 and E 4 simultaneously hold. Furthermore, assume thatη ≤ 2 -1 T Ĉ2 2 2D C (4) α,D ln(6M/δ) + ρ -1holds. Then, the following inequalities hold for any t ∈ [T ] and j ∈ [J]:EQUATIONEQUATION)where k is defined in Lemma B.5. Furthermore, the constants Ĉ and C Proof. From the definition of Lt (θ), we haveEQUATIONwhere Eq. ( 222) follows from Lemma B.13. Therefore, Lt (θ)is 2 t Ĉ2 2 2D C (4) α,D ln 6M δ + ρ - smooth function. Furthermore, Lt (θ) is 2ρ-strong convex because ∇ 2θ Lt (θ) ⪰ 2ρI p holds. By combining the definition of η with the standard result of gradient descent for the strongly convex and smooth objective function (e.g., Theorem 3.6 in [16] ), Lt ( θt;j ) ≥ Lt ( θt;j-1 ) holds for any j ∈ [J]. Therefore,EQUATIONwhere Eq. ( 226) follows from the event E 4 . Furthermore, since the unique minimum of Lt (θ) is given as θ * := θ 0 + ρI p + G t G ⊤ t -1 G t y t , we have the following inequalities from Theorem 3.6 in [16] :θt;j -θ 0 -ρI p + G t G ⊤ t -1 G t y t 2 2 (227) ≤ (1 -2ηρ) j ∥θ 0 -θ * ∥ 2 2(228)EQUATIONwhere:• Eq. ( 229) follows from ∇ Lt (θ * ) = 0 and the fact that Lt is the 2ρ-strong convex function.• Eq. ( 230) follows from Lt (θ * ) ≥ 0.• Eq. ( 232) follows from the event E 4 .Lemma B.10(Adapted from Lemma C.3 in [41]). Fix any R ≥ 0, j ∈ [J] and t ∈ [T ]. Suppose that the learning rate η satisfies η ≤ 4 -1 ρ + 2(2R + 2 D Ĉ) 2 T C (4) α,D ln 6M δ -1, and θ t; j satisfies∥θ t; j -θ 0 ∥ 2 ≤ R for all j ∈ [j]. Furthermore, assume that R satisfies the following inequality:EQUATIONwhere:EQUATIONThen, under the events E 2 and E 4 ,EQUATIONwhereh t;j = [h(x 1 ; θ t;j ), . . . , h(x t ; θ t;j )] ⊤ ∈ R t .Proof. We first assume that ∥h t;j -y t ∥ ≤ kB + σ 2 ln 12T δ √ 3t holds. Here, by resorting the same arguments as the proof of Lemma C.3 in [41] , for any θ, θ ′ ∈ R d such that ∥θ -θ 0 ∥ ≤ R, we haveEQUATIONEQUATIONwhere e(θ ′ , θ)EQUATIONEQUATIONwhereEQUATIONα,D ln 6M δ ∈ (0, 1). Furthermore, for any θ ′ ∈ R p , we obtain the following inequality by combining the lower bound of L t (θ ′ ) -L t (θ) with the above inequality,EQUATIONwhere the second inequality follows from the Peter-Paul inequality, and the last inequality follows from ∥h t (θ) -y t ∥ 2 2 ≤ L t (θ). Rearranging the above inequality with θ = θ t;j and θ ′ = θ 0 , we haveEQUATIONThen, from Lemma B.15,EQUATION(248)EQUATIONEQUATIONEQUATIONFurthermore, from ∥h t;j -y t ∥ 2 ≤ kB + σ 2 ln 12T δ √ 3t, we haveEQUATIONEQUATIONEQUATIONCombining the above inequality with Lemma B.15, we haveEQUATIONTherefore,EQUATIONEQUATIONwhere the second line follows from the fact that 8cηρ + 2 ≤ 1/(cηρ) holds due to ηρ ≤ 1/4 and c ∈ (0, 1). Furthermore, the last line follows from the condition (233) with c ≥ 3/4. By combining Eq. (245) with Eq. (261), we haveEQUATIONEQUATIONBy combining the event E 4 with the above inequality, we obtain the desired inequality.Finally, we check the assumption ∥h t;j -y t ∥ 2 ≤ kB + σ 2 ln 12T δ √ 3t. If j = 0, ∥h t; j - y t ∥ 2 ≤ kB + σ 2 ln 12T δ √ 3tclearly holds from the event E 2 and h t;0 = 0. Here, by applying the aforementioned arguments, we can also verify ∥h t; j -y t ∥ 2 ≤ kB + σ 2 ln 12T δ √ 3t for j = 1. Repeating the same arguments for j = 2, 3, . . . , j, we obtain the inequality ∥h t;j -y t ∥ 2 ≤ kB + σ 2 ln 12T δ √ 3t.Lemma B.11 (Adapted from Lemma B.2 in [41] ). Suppose the following inequalities hold:EQUATIONEQUATIONEQUATIONwhere:EQUATIONEQUATIONFurthermore, we set Cα,D,T asEQUATIONEQUATIONThen, under the events E 2 , E 3 , and E 4 , the following inequalities hold for any t ∈ [T ] and j ∈ [J]:EQUATIONEQUATIONProof. We show by induction. Let us define G t;j and h t;j as G t;j = [g(x 1 ; θ t;j ), . . . , g(x t ; θ t;j )] ∈ R p×t and h t;j = [h(x 1 ; θ t;j ), . . . , h(x t ; θ t;j )] ∈ R t , respectively. First, Eqs. ( 273) and (274) clearly hold if j = 0. Next, fix any j ∈ [J], and suppose that Eqs. ( 273) and (274) hold for any j < j. Then, as with Lemma B.2 in [41] , we haveEQUATIONBy resorting the similar argument of the proof of Lemma B.2 in [41] , the first term is bounded from above as follows:EQUATION)As for the second term of Eq. ( 275), from Lemma B.10 and Lemma B.15, we haveEQUATIONEQUATIONEQUATION• Eq. ( 280) follows from Lemma B.10, the condition (267), and the induction hypothesis.• Eq. ( 281) follows from the event E 3 and the induction hypothesis.Furthermore, from Lemma B.13 and Lemma B.15, we haveEQUATIONEQUATIONEQUATIONBy combining Eqs. ( 276), (281), and (284) with Eq. ( 275), we haveEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONwhere Eq. ( 289) follows from the condition (268). From the triangle inequality and Lemma B.9,EQUATIONEQUATIONLemma B.12 (Adapted from Lemma C.1 in [24] ). Under the event E 5 , the following inequality holds for any t ∈ N + :EQUATIONwhere the constant Cα,D is defined in Lemma B.6.Proof. Fix any x 1 , . . . , x t ∈ X . Then,EQUATIONEQUATIONEQUATION• Eq. ( 295) follows from the concavity of ln det(•) and the fact that ∇ X ln det X = X -1 holds for any symmetric matrix X. In Eq. ( 295), ⟨•, •⟩ represents the matrix inner product.• Eq. ( 296) follows from the definition of γ t .• Eq. ( 297) follows fromI t + ρ -1 K t -1 F ≤ I -1 t F ≤ √ t.• Eq. ( 298) follows from the event E 5 .Lemma B.13. Let us define G t (θ) as G t (θ) = (g(x 1 ; θ), . . . , g(x t ; θ)) ⊤ ∈ R p×t . Then, under the event 2 , the following inequality holds for any R ≥ 0, t ∈ N + , and θ ∈ R p such that ∥θ-θ 0 ∥ 2 ≤ R:EQUATIONwhere the constants Ĉ and Cα,D are defined in Lemma B.4.Proof. From the definition of ∥ • ∥ F , we haveEQUATIONHere, the last inequality follows from the condition E 2 .Lemma B.14. Under the event E 2 , the following inequality holds for any t ∈ N + :EQUATIONwhere the constants Ĉ and Cα,D are defined in Lemma B. 4 .EQUATION)Proof of Theorem B.1. Suppose that the events E 1 -E 6 hold. As proposed in [30] , we decompose the error term |f (x) -h(x; θ t )|:EQUATIONBy combining the event E 6 with Lemma B.12, the first term of Eq. ( 317) is bounded from above as follows:EQUATIONEQUATIONEQUATIONFurthermore, we obtain the following inequalities for the second term:EQUATIONEQUATIONEQUATIONEQUATIONwhere:• Eq. (322) follows from the feature space representation of μt . Actually, we have μt(x) = g(x; θ 0 ) ⊤ G t (ρI t + G ⊤ t G t ) -1 y t = g(x; θ 0 ) ⊤ ρI p + G t G ⊤ t -1 G t y t ,where the last equality follows from the matrix identityG t (ρI t + G ⊤ t G t ) -1 = ρI p + G t G ⊤ t -1 G t(e.g., Lemma 3 in [29] ).• Eq. (323) follows from the fact that ⟨z 1 ,z 2 ⟩ ≤ (z ⊤ 1 A -1 z 1 ) • (z ⊤ 2 Az 2 ) ≤ (z ⊤ 1 A -1 z 1)∥A∥ 2 ∥z 2 ∥ 2 holds for any positive definite matrix A ∈ R p×p and z 1 , z 2 ∈ R p .• Eq. (324) follows from σt (x)EQUATIONα,D , where the last inequality follows from the event E 5 .• Eq. (325) follows from Lemma B.9 and Lemma B.11.By using Taylor's theorem for the third term, there exist a ∈ [0, 1] such that:EQUATIONwhere Eq. (327) follows from h(x; θ 0 ) = 0 holds for any x ∈ X , and Eq. ( 330 η ≤ 4 -1 ρ + 2(2 R + 2 D Ĉ) 2 T C (4) α,D ln 6M δ -1, with probability at least 1 -δ, the following inequality holds:EQUATIONEQUATION)where β is defined in Theorem B.1. Furthermore, if M and J is sufficiently large to satisfy the following additional three conditions:EQUATIONEQUATIONEQUATIONthen,EQUATION)The proof of Theorem C.1 leverages the following lemma, which describe the relation between the sum of σt-1 (x t ) and MIG.Lemma C.1 (Lemma 5.3 and Lemma 5.4 in [32] ). Fix any T ∈ N + . Then, for any sequence x 1 , . . . , x t , the following inequality holds:EQUATION)Proof of Theorem C.1. From Theorem B.1, with probability at least 1 -δ,EQUATIONEQUATIONEQUATIONwhere Eq. ( 339) follows from the definition of x t , and Eq. (340) follows from Lemma C.1. Furthermore, Eq. (341) follows from Lemma B.12.Proof. Fix any function f ∈ H TNTK . According to Mercer's representation theorem (see, e.g., Theorem 4.5.1 in [33] ), there exists a sequence (w n,j ) such thatEQUATIONFurthermore, the RKHS norm ∥f ∥ TNTK is obtained as ∥f∥ 2 TNTK = ∞ n=0 N d,nj=1 w 2 n,j . Note that, similar to the TNTK, the ReLU-based NTK can be expanded using spherical harmonics (Y n,j ) as follows (see, e.g., [35] ):EQUATIONwhere ( λn ) n∈N are the eigenvalues of the NTK. Here, the function f can be written asEQUATIONBy noting both TNTK and NTK can be expanded by (Y n,j ), the following equation holds from Mercer's representation theorem:EQUATION)According to Bietti and Bach [6] , λn = Θ(n -d ) and there exists a constant C d,L > 0 such that C d,L n -d ≤ λn . Combining this with Lemma 3.1, we have:EQUATIONSince n d exp -ln 1 + 1 4α 2 Dn → 0 (as n → ∞), there exists a constant C α,d > 0 such that n d exp -ln 1 + 1 4α 2 Dn ≤ C α,d holds for any n ∈ N. Thus,EQUATION)From the above, it follows that H TNTK ⊂ H NTK .Definition E.1 (Sub-Gaussian norm, Definition 2.5.6 in [39] ). Let X be a real-valued random variable. Then, the following quantity ∥X∥ ψ2 is called the sub-Gaussian norm of X:EQUATION)Moreover, if ∥X∥ ψ2 < ∞ holds, we call the random variable X a sub-Gaussian random variable. Definition E.2 (Sub-exponential norm, Definition 2.7.5 in [39] ). Let X be a real-valued random variable. Then, the following quantity ∥X∥ ψ1 is called the sub-exponential norm of X:EQUATIONMoreover, if ∥X∥ ψ1 < ∞ holds, we call the random variable X a sub-exponential random variable. Lemma E.1 (General Hoeffding's inequality, Theorem 2.6.2 in [39] ). Let X 1 , . . . , X N be independent, mean-zero, sub-Gaussian random variables. Then, for every t ≥ 0, the following holds:EQUATIONwhere c > 0 is an absolute constant. Lemma E.2 (Bernstain's inequality, Theorem 2.8.1 in [39] ). Let X 1 , . . . , X N be independent, meanzero, sub-exponential random variables. Then, for every t ≥ 0, the following holds:EQUATIONwhere c > 0 is an absolute constant. Lemma E.3 (Centering, Lemma 2.6.8 and Exercise 2.7.10 in [39] ). For any sub-Gaussian random variable X, ∥X -E[X]∥ ψ2 ≤ C∥X∥ ψ2 holds. Furthermore, for any sub-exponential random variable Y , ∥Y -E[Y ]∥ ψ1 ≤ C∥Y ∥ ψ1 holds, where C > 0 is an absolute constant. Lemma E.4 (Product of sub-Gaussians is sub-exponential, Lemma 2.7.7 in [39] ). Let X and Y be sub-Gaussian random variables. Then, XY is a sub-exponential random variable whose subexponential norm satisfies ∥XY ∥ ψ1 ≤ ∥X∥ ψ2 ∥Y ∥ ψ2 .Here, we provide additional information on the implementation of the ST-UCB and NN-UCB algorithms. Our implementation includes the following three simplifications:(a) In the calculation of the gradient in line 5 of Algorithm 1, we use g(x; θ t-1 ) from the previous round, rather than the initial gradient g(x; θ 0 ). (b) In the regularization of parameters in line 3 of Algorithm 3, we do not consider the residual from the initial parameters θ 0 . In other words, we apply L2 regularization directly to the parameters themselves. (c) Instead of initializing θ 0 as described in Sec. 3.1, we initialized θ 0 by the Glorot's uniform initializer [17] .It should be noted that the simplification (a) is the same implementation as the original NN-UCB, while the other simplifications are for the sake simplicity in implementation. We train two models (ST, NN) using stochastic gradient descent (SGD) with a momentum term. The learning rate and the momentum are set to 0.01 and 0.9, respectively. When the momentum is greater than zero, past gradients are considered as a weighted average. SGD is performed in all rounds, with a mini-batch size of 64 and 5 epochs, and we do not use early stopping.In the results shown in Fig. 2 of the experimental section, we presented the outcomes with optimal hyperparameters of ϵ, β. Here, the experimental results for each parameter ϵ ∈ {0.05, 0.1, 0.2}, β ∈ {0.01, 0.1, 1} are summarized in Fig. 3 (real-world dataset) and Fig. 4 (synthetic dataset). In most cases with the real-world dataset, as the rounds progressed, ST-UCB demonstrated better performance than NN-UCB, and UCB-based policies outperformed ϵ-greedy based policies when β = 0.01. In the f (1) setting for the synthetic data, the regret of ST-UCB converged the fastest. On the other hand, in the f (2) and f (3) settings, NN-UCB sometimes performed well, however the trend of cumulative regret over the rounds was comparable between ST-UCB and NN-UCB.Our analysis relies on the TNTK derived by Kanoh and Sugiyama [21] . From the definition of the soft tree ensemble model, we haveEQUATION) If θ ∼ N (0, I p ), (⟨∇ θ (m) h(x; θ (m) ), ∇ θ (m) h(x; θ (m) )⟩) m∈[M ]is mutually independent; therefore, from the law of large number, the inner product⟨∇ θ h(x; θ), ∇ θ h(x; θ)⟩ converges to E[⟨∇ θ (m) h(x; θ (m) ), ∇ θ (m) h(x; θ (m))⟩] in probability as M → ∞. Kanoh and Sugiyama [21] shows that E[⟨∇ θ (m) h(x; θ (m) ), ∇ θ (m) h(x; θ (m) )⟩] equals the expression in Eq. ( 1) by relying on the recursive expressions of the soft tree (such as Eq. ( 81)).As described in Section 3.2, MIG is commonly used as the problem complexity parameter of the kernel-based decision-making problem. On the other hand, instead of MIG, some existing works quantify the problem complexity based on the following effective dimension d [10, 37, 40, 41] :EQUATIONDue to the following inequality [9, 10] , the MIG is bounded from above by the worst-case effective dimension up to logarithmic scale:EQUATIONNeurIPS Paper Checklist Justification: The assumptions for our main result are given in Assumption 3.1, and the discussions of their validities are described in Remark 3.1. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 


Decision: This paper proposes a new bandit algorithm where the reward function is estimated with a soft tree ensemble method. The authors present their model as an extension to NN-UCB but with sublinear regret guarantees at the cost of a reduced hypothesis space. The generalized theory of neural tangent kernels, i.e. the tree neural tangent kernel, was utilized in a similar fashion as neural tangent kernel were used in previous works for the NN-UCB algorithm. Numerical results are provided at the end of the paper.

The reviewers agree that there is more merit in this paper than its limitations. In particular, the proposed soft tree based USB has better theoretical guarantees than NN-UCB, the current state of the art (this, however, comes with a cost).  On the other hand, the key weakness of the paper is its presentation. In its current format there a numerous unclear parts. If this paper gets accepted, I strongly recommend the authors to polish the paper to improve the readability of the text.

Reviews: review: paper_summary: paper_summary: The paper investigates soft tree ensemble model for reward modeling in bandit algorithms.
strength_weakness: strength_weakness: Not sure if there is some new insights beyond other similar works that utilized the NTK theory such as Neural Thompson Sampling.
questions: questions: (1) Could you share more insights on why soft tree ensemble model is of particular interest? In which case we should prefer tree-based reward model than ReLu-based reward model?
limitations: limitations: The paper did discuss the theoretical limitation.
paper_summary: paper_summary: This paper presents the Tree Neutral Tangent Kernel (TNTK) for soft tree models and introduces the ST-UCB algorithm based on this kernel. The authors also provide theoretical guarantees for the kernel and algorithm, including a regret bound. The contribution of this study is substantial; however, many sections require further refinement to enhance the clarity and overall presentation.
strength_weakness: strength_weakness: A piece of the main contribution is the introduction of TNTK and its theoretical properties. But, these are not presented well. A more detailed and clear description for the introduction of TNTK seems necessary. Even the definition is missing. The authors should show the derivation steps of TNTK in a more structured way. There are some other problems with presentation:

- The first paragraph in the first section is unclear. How various combinations of users and items can be connected to unobserved actions?
- Lines 42-53 are not clear. The authors should explain the effective dimension more or describe the bounds in terms of the ambient dimension d.
- Citation formats should be corrected.
- For Section 2, lines 107-120 should be clearer. Especially, lines 111-113 seem to have some errors.
- The proofs in Appendices need much work for improved presentations.
- The statement of Lemma 4.1 seems wrong.
questions: questions: - For the subGaussian assumption in Assumption 3.1, do we need the conditional expectation given H_t-1? Due to the independency of noise, it does not seem to be necessary. If needed, could you please explain?
- The exponential eigenvalue decay is surprising. Could you please provide some intuition on how the improvement can be achieved as compared to NTK?
- What is the key difference between NN-UCB and ST-UCT in their mechanism?
limitations: limitations: The derivation of TNTK does not seem markedly different from that of the Neural Tangent Kernel (NTK), which may slightly weaken the perceived novelty of the study. Nonetheless, the application of mathematical techniques used for NTK to develop TNTK is not straightforward and still represents a significant contribution.
paper_summary: paper_summary: The paper proposes an algorithm for multi-armed bandits, where the reward function is estimated with a soft tree ensemble method. The paper present their model as an extension to NN-UCB but with sublinear regret guarantees at the cost of a reduced hypothesis space. The generalized theory of neural tangent kernels, i.e. the tree neural tangent kernel, was utilized in a similar fashion as neural tangent kernel were used in previous works for the NN-UCB algorithm. Numerical results are provided at the end of the paper.
strength_weakness: strength_weakness: In line 218 wihtin Theorem 3.2: a concrete dependency on T for the lower bound on M would have been nice, in order to insert it into Theorem 3.2 to see how the confidence bound depens on time. Without that a reader could think that the confidence bound is super linear in T.

Minor errors: in Lines 112 and 113 I think the gradient operators are missing within the inner products. Line 124 should have bold g in the inner product.
questions: questions: The theory suggests that the regret bound improves with increasing M. Is there a point where M is to large and the tree ensemble becomes too complex?
limitations: limitations: The paper clearly indicates that the imrpovement they make over exisiting work comes at the cost of a reduced hypothesis space.
paper_summary: paper_summary: This thesis presents a stochastic bandit algorithm ST-UCB based on the soft-tree ensemble model for reward estimation and regret minimization. This algorithm exploits the properties of the soft-tree model and extends the neural robber theory to a tree-based structure, proving that under appropriate assumptions, ST-UCB achieves lower cumulative regrets, demonstrating superiority over the traditional robber algorithm based on ReLU neural networks. In addition, this paper explores the theoretical connection between soft and hard trees, and proposes the prospect of tree-based modeling in complex data analysis.
strength_weakness: strength_weakness: Although the paper proves that the ST-UCB algorithm achieves regret-free performance under specific regularity conditions, these conditions may be difficult to satisfy or validate in practical applications.
questions: questions: It is recommended to explore the applicability of the algorithm under a wider range of conditions and to focus on the efficiency of the soft-tree model, taking into account the complex structure and high computational demands that may be involved.
limitations: limitations: Authors have discussed the limitations.

Comments: comment: I thank the authors for their detailed response.
Dear reviewers,

We would like to thank you for taking the time to review the manuscript.
We truly appreciated your valuable comments and suggestions, which helped us improve the clarity of the paper.
We hope that our response resolves the reviewer's initial concerns and clarifies any ambiguous points about our paper.
If you have any further questions or concerns, please let us know. We will make an effort to provide additional responses throughout the duration of the discussion period.
I thank the authors for the detailed answer to my question. I decided to leave my score as it is and wish the authors good luck.