No-Regret Bandit Exploration based on Soft Tree Ensemble Model
Authors: Shogo Iwazaki
Shinya Suzumura
Venue: NeurIPS 2024 poster (2024)
Keywords: neural bandits; tree ensemble model; kernel bandits;
Primary area: bandits

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.

No-Regret Bandit Exploration based on Soft Tree Ensemble Model
Shogo Iwazaki LY Corporation Tokyo, Japan si Swwazaki@lycorpp co.
Shinya Suzumura LY Corporation Tokyo, Japan
ssuzumur@lycorp.co..
Abstract
We propose 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 soft brse-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 ReLU-based neural network.
Introduction
The stochastic bandit framework is 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 vast action space generated by various combinations armed bandits 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 [2), kernel regression [I [2], and neural networks [3 41), which are referred 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.
users and items [38]. Standard algorithms designed for finite-
Motivated by these considerations, this paper explores the stochastic bandit algorithm using tree ensembles, 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 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 Lipschitz continuity of rewards is explored in Lipschitz bandits [8), linearity of rewards is examined in LB 52). and more generally, the assumption that rewards lie in a known reproducing kernel Hilbert space (RKHS)
studied in KB [1] 32.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Our paper studies type of bandit algorithm that employs a tree structure model, topic with limited prior exploration. Féraud al. [[5] proposed 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-sty algorithm utilizing decision trees; however, their algorithm's 's construction relies on heuristics and does not provide 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 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-))/d) resulting in super-linear growth of (dv/T) regret, which becomes meaningless [23]. Several studies address this issue by employing algorithms in the form of a
sup-variant of UCB [37] phased climination-style algorithms [6).. proving a regret upper bound
of (((((ddd1)) 1)/ (2d)
30). These studies combine theoretical analysis via the neural tangent 19 for DNN regression with regret analysis techniques from KB, constructing algorithms and performing regret analysis. Our proposed algorithm can be seen generalization of NB theory using a soft-tree regressor from DNN.
23
24
kernel (NTK) 4
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 the existing NN-UCB algorithm [41], incorporating the theory of the tree neural tangent kernel (TNTK) in soft trees (11 22) To our knowledge, this paper
represents the first effort to extend the theory of NB to a rrce-based structural model.
we derive several non-trivial properties of the soft tree ensemble model. These include the decay rates of cigenvalues of the TNTK (Lemma B.1p. concentration properties of TNTK (Lemma 3.2). and upper bounds on the spectral norm of the Hessian matrix (Lemma B.3). Leveraging these results, we demonstrate that the ST-UCB algorithm achieves regret of ((VT) under appropriate regularity conditions.
In Sec. 3.2.
Sec.B.2
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 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.
2 Preliminaries
Problem setting. We consider sequential drciision-maiing problem whose goal to maximize the total reward under bandit feedback. Let f X + R be an unknown reward function, where X' C Rd a finite set of action candidates. At each time step f, the environment reveals an action set X, C X; thereafter, the learner chooses an action æ; and receives the corresponding reward y1 = f(x;) + fts where 6 is noise random variable whose mean is zero. As a performance metric, we adopt the pseudo cumulative regret Ry := If=1(f(;)) [fx;) - (xx)). where x; E arg max
In our problem setup, the action set X, is allowed to change at each step In addition to the standard bandit setup that assumes X4 = X,, this formulation includes a contextual bandit setup by setting X, ((c,, a) A(c:)), where e; is context vector step 1,, and A(ce) is the corresponding action set.
Soft tree ensemble. At each time step I, 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, us consider M E N. perfect binary trees whose depths are D E N4. Note that each tree has N = 2 internal nodes and L = 2n leaf nodes. Furthermore, for technical reasons, assume

---

M22
CRR
#1
2
AiDoming (12 (122)))) (x (1r -(1
Figure I: An illustrative image of soft tree structure with D = 3. As shown in the left plot, we have N := 2 internal nodes (green) and L == 2 leaf nodes (orange), indexed using breadth-firs: ordering. The right plot shows illustrative example where soft tree calculates the weight probabilities pr (-) for the leaf nodes.
(m) that M an even number. Let wa E Rdd and mi. E IR be the parameters of the n-th internal and I-th leaf node of the m-th tree, respectively. We index these parameters according to breadth-fin
[ Moreover, we also denote all internal and leaf node R-, The output of a standard decision tree is obtained as the parameter of some leaf node, which 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 probabilistic one. Specifically, given parameters the corresponding output h(æ;; ((m) of the m-th soft tree defined as
ordering, as described in the left plot of Fig.
parameters as (m)) ;= (w] (m))
(m)) E RR- and (1m) = (T] (m)
[ (T)))
wx V
((m) == (w (m)T x ((m)T)T and any input æ E X,
NV
h(#;; 0 (m))
(m) mi (x (m)), where pr(;;; ()) = II r=m
o (w,, x) I// aw xx) Iasa
Here, / and In I indicator functions. If the [-th leaf node belongs to the left (resp. right) sub-tree whose root is the n-th internal node, / (resp. I,) is one; otherwise, zero. Furthermore, a(.) R + [0, 1] is soft decision function. The right plot of Fig. shows illustrative image of the calculation of p-()). As with 21 we use the scaled error function a (w,, x) = jerf(aww, x)) +
with some pre-specified scaling parameter a 2 O, where eri(b) 7 1o exp(-2²)dz for any b E R. By aggregating M soft trees, the whole output ha:;; 0) of the soft tree ensemble model is defined as h(2;; 0) = >m Tı( 0(()), )/v M,, where 0 = (0) model structures as described above, the training of the model parameters 0 is conducted based on the gradient descent optimizer, which aims to minimize some pre-specified loss functions. In our algorithm, adopt regularized square loss, whose detailed definition is given in Sec. 3.1
((A)T)T E Md((++++) Under the
Neural tangent kernel theory for overparameterized model. The neural tangent kernel (NTK) [19 is an effective theoretical tool for understanding the learning properties of overpa- rameterized neural networks. Let hxx(::0) Rd - IR be feed-forward neural network with ReLU activation function, L hidden layers whose width is M, and network parameters O. Given any fixed inputs æ, ã E IRd, and O, ~ NN I), it has been shown that the inner prod- uet (VohNn (z: Og), V VohNN (ē; Qo)) of gradients converges (i.e.. (VehNN(æ; 0o), VohNN (æ:; 0o)) I (x, Ø) as M + 20). The kernel function λNTK is called the NTK. Moreover, in the overparameterized regime, INN(;;;) 0) trained with gradient descent with an infinitesimally small learning rate coincides with the kernel ridge-less regressor hNTK (æ). whose kernel function is ÁNTK 4. This property motivates us 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 KB. In our paper, we consider soft tree variants of these existing works.
fixed kernel function kNIK (z, a)
Recently, Kanoh and Sugiyama 21 generalized the NTK theory to the soft tree ensemble model. Let g 0) = Veh(w; 0) Rº be the gradient vector of the soft tree ensemble model at parameter
3

---

Algorithm The soft tree-based upper confidence bound (ST-UCB) algorithm
Input: X C F D E N+. N+, 7 > 0, > 0, a > 0, M E N+, T N+, 5 0.
1: Initialize 0 randomly described in Sec. 3.1
2: Define G. = 0 E RR.
3: for |= 1, ..... 7 do
4: Obtain X
5: Calculate 07- 1 (x) = g(: (a) [Tp + G g(;; 0o) on X.
6: 3y +- arg max [b(2; 111 + 16;-1(xx))
aEA:
7:
Obtain y/ f(z) + c..
8: (rainST (t. U. (o,, (e J. 17, p. D, m).
9: Define G. g 1 On). (z; 0n)] E Rxxt
10: end for
Algorithm 2 TrainST (L, Oo, (æts, yi yi)ie D, ox M)
1: 00,0 +- Oo
2: for j I,....JJ do
3: Calculate gradient of (0(00=11) = Ei= [1(x;;; Oug-1) - w/l + p110 -0o11.
4: Update parameter: 0:g f- 01j-1 (VVo
5: end for
6: return 1z.J-
E RP, where = M(dN + ..) denotes the total number of parameters. Then, given fixed inputs I E X' and 0g ~ No0, Ip), the inner product (g(x, Bu), P fo)) has also been shown to converge in probability some kernel function kYNTK (x, )) as the number of ensemble models M grows infinitely (see Theorem in (2l)). This limiting kernel kINIK is called the tree neural tangent kernel (TNTK) as an analogy to NTK and is defined as follows:
kTNTK( 2) 2P (T P-) 2) (2T(x,
(1)
where:
a²xTa
T(x,
x)
aresin
+ 4
(2)
2m
V (a + 0.5) ã + +.5)
a²
T(x, x))
(3)
(1+ 2 x1 20 x)
4a xx TT)
should be noted that even we follow the existing NTK-based techniques of NB, generalizing the result of Kanoh and Sugiyama (21) the analysis of sequential decision-making tasks is non-trivial. Specifically, the existing analysis of NB heavily relies on the following results 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 maximum information gain (MIG) of NTK (35), which measure the complexity of the KB problem depending 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
3.1 Proposed algorithm: ST-UCB
The pseudo-code of our proposed algorithm, soft tree-based UCB (ST-UCB), is shown in Algorithm ST-UCB 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 O, E E' for the gradient descent method as follows. Let Ousee ~ ((..Ip/2) ) be base initial parameter, with p = MdN L).
Using Orase. we set the initial parameters On as Oo = (0 O OT) where 0o+ E IRP/2
and Po- E IRP/2 are defined as 00+ = (w base " base
(1)T (1)T
w huse buse DT and On- =
(M/2)T
respectively. This initialization procedure ensures that the initial model output is 0 (i.e., h: 0o) = 0 for all æ E 2),, which is essential for our theoretical analysis.
(wo (A1/2+1)T base
(M/2+1)T ..... base
(M)T base
(M)
Learning. At each step t, ST-UCB learns the model parameter 0 based on regularized squared loss (0) = E (M( - y1)² + pll0 0oll.. where p >> is a regularization parameter.
UCB-based selection of xy At each step t. ST-UCB selects x, as follows:
Dt E arg max [h( (x; 11- 1) +
(
xE
g 0b) with g 0) == Voh(x;; 0) R' and Gt-1 (g( 6o). ..... (1: 00)) E Rext In ST-UCB, the quantity of (ar) quantífies the uncertainty of the model output h(:: 0.) and is essential for the construction of confidence bounds. Furthermore, the quantity o2- (x) is interpreted as the predictive variance of a Bayesian linear regression whose feature map is the gradient of the initial model output (a:;; 0o). We note that a
where (z) g(;; Bo) (Ip - GG.
similar quantity is leveraged in existing NB algorithms 223 30
3.2 Theory of ST-UCB
Assumptions for theoretical analysis. We make the following assumptions for our theory:
Assumption 3.1. (i) The output noise e conditionally r-sub-Gaussiie for some a > Specifically,
Elexp(Acx) H4-11 S exp(X>o² /2) holds for any t E [T] == fI....,T) ; and any history H = (00,))) 1t 1t- (ūi The inpul space X C Rdd is subset of the hyper-sphere S = {ar E Rd || = 13. (iii) The underlying reward function f is an element of the RKHS corresponding to kYWIK, where KINTK 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- < cc. That is, [|f]TTTKK I B holds, where II. TNTK denotes the RKHS norm corresponding to KTNTK-
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 123 24 30 40 41 and holds without loss of generality by transforming the original input space through bijection map. For example, given any original input space X' C Rd, we can construct new input space X on the hyper
sphere Sd as X x= (11
| C Sd, where I = mmx 1|01|22
Assumptions (ùi) and (iv) are similar to those in existing NB works 123 24 30y. 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 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 "rr as
TT
max In det (Ir + p- p''Kk) Ex
(5)
2
5

---

where K7 is the T x T kernel matrix whose (2.j)-th entry is ( 2y) This Pr is called the maximum information gain (MIG) since the quantity 0.5 det [ + p- ) is equal to the information gain from T observations in a Gaussian process regression model, characterized by the covariance function KTNTK and the noise variance parameter [32]. The following Theorem 3.1 is our main result about MIG, which shows that "TT grows logarithmically.
Theorem 3.1 (Upper bound MIG of TNTK). Fix any a (0, oo), 2 2, D E N4, and X C Then, YT = OIn T). Here, the implied constant depends on a, and DD
The proof of Theorem 3.1 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 cigenvalues, which plays a central role in the proof of Theorem 3.1
Lemma 3.1 (Figendecompositionn of TNTK), Fix any 2 2, a E (0, and 'D E E Furthermore, n + --3
let us define Na.; as Na,n 2m-
for any n N, where a
(1)
bi(a by! is
d-2
binomial coefficient. Then, for any x, ã E S0-1, the TNTK corresponding to a and satisfies
00 Na.
bYNTK (z, x)
ΣΣ
R=0 j=1
where (Nn) and Nee, are eigenvalues and eigenfunctions of (the integral operator of) TNTK that satisfy Ao 2 X1 2 ... O. In addition, for any n. E N, the eigenvalue X satisfies
(-nD In (1 4a² 1122) ))
An < C.p exp
where c(U) > O is a constant, which depends on a and D.
Remark 3.2. The eigenfunctions (Yn.)jj(NNan are known spherical harmonics of degree n with multiplicity Na. (see, e.g.. [T3). Furthermore, on the hyper-sphere gd-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.
16 35%, while corresponding eigenvalues differ from those of TNTK.
The proof of Lemma 3.1 is given in Appendix A. Lemma 3.1
demonstrates the exponential eigenvalue decay of TNTK, in contrast to the polynomial eigenvalue decay of NTK with ReLU activation 6 335 This difference leads to faster convergence of ST-UCB compared to NN-UCB, albeit with smaller corresponding RKHS of TNTK. We discuss more details in Sec. 4
Confidence bound.
The following shows the confidence bounds for the soft tree-based model.
Theorem 3.2 (Confidence bounds based the soft tree ensemble model). Suppose Assumption 3.1 holds. Fix any 8 E (0,1), p > O, a 2 1, and D Z 2. Let KTNTK(X)) = [KTNTK (x, d))x, E
| and An = Amin (KTNTK( (X)) > 0 be the kernel matrix over X x X and the minimum eigenvalue of KTNTK(A (2), respectively. If the number of soft tree ensemble models M is sufficiently large satisfy M Poly(T,p-* B, B.B.o
2n AA=' |21, In (((1))) and the learning rate n satisfies n S O((T2240 a² (/(M + -1),, then, the following event holds with probability at least 1 - 5:
T (I) M) + -()))1(2)),
VE [T Ye E 1f()) h1:; 50
(8)
VM
where:
B B=0 0-0(VT-
73/2
( (P(I M3/2) 73/ (In
11/2
VM
Remark 3.3. The minimum eigenvalue No of the kernel matrix of TNTK is guaranteed to be strictly positive if X C. gd-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 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 soft tree versions of their results.
we provide the following
Lemma 3.2 (Concentration to TNTK). Fix any a, sd-11 8 e (0, 1), and E (0, Ca,D! with (23 (212
c.2 a 22 M 2 Ö max a.D
22 J (161//)), then,
P(ITTNKK(E .) (g( 0o), g ã. Bo)) - 4<) 2 1-6,
(10)
where 0o is the initial parameter of ST-UCB, and C, C 0 are absolute constants.
Lemma 3.3 (Spectral norm upper bound). For any å E (0, 1) and a 2 1, with probability at least
1 8, the following holds for any R > 0, IR, and sd-1;
(33)
RR + 22)² 2D42
100 - 0oll2 S R (x, 0)1 S aD
(11)
VM
where H(x 0) VBa2220 Furthermore, for any A E RPxp, ||||| == max || denotes the spectral norm.
0) E2XP is the Hessian matrix of the model output, and Cou
The proofs of Lemma 3.2 and Lemma 3.3 are given in Appendix B By carefully combining Lemma 3.2 and Lemma 3.3 with the existing proof strategy of NB, we derive Theorem 3.2 The
overview of the proof is summarized in Appendix B.3.1
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 ((VT) regret upper bound for ST-UCB as stated in the following theorem. The proof is provided in Appendix
Suppose that Assumption 3.1 holds. Fix any 8 E (0, a 2 1. O, and D 2 Furthermore, assume that the confidence width parameter B 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 2 Poly(T, B, a, a,22, ./0 In(1 /8)), and the learning rate nl satisfies S O(T2220 a² (n(M/ + ))), then, the following holds with probability at least 6 6:
Theorem 3.3.
V2B+ 11+ の 2
8T +1)
O (VTInnT). (12)
R 11
Vp /
In p---)2
4 Comparison of NN-UCB and ST-UCB
Comparison of regret. In the existing NN-UCB algorithm 41, a regret upper bound of OddVT) 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 equivalent up to logarithmic dependencies [37]. Considering the upper bound on MIG of NTK, ((NTK)
(dT(d)))/d) 23
35 the regret of NN-UCB becomes O(7(4-1)441/23)-- ((,, VT)). This results in super- linear regret, and meaningful guarantees for NN-UCB are not achievable without further restricted assumptions on the input set Xx (e.g., see the discussion in Appendix D in [40]). To address these issues in general setting, it is necessary to construct more complex algorithms that incorporate concepts such as sup-variant of UCB [2 30 or phased elimination (4), yielding a regret upper
(NTK).
(TNTK) diverges bound of (6V 77 (NTK)T). In contrast, due to Theorem 3.1 the MIG of TNTK TT
on a logarithmic scale. Therefore, ST-UCB achieves regret bound of ((VT) without requiring additional assumptions the input set X,, maintaining simple UCB-style algorithmic structure.
7

---

Comparison of hypothesis space. In our analysis, we assume in Assumption 3.1 that the reward function f belongs the RKHS HTNTK associated with TNTK. Conversely, in existing NB research. it is assumed that f' belongs to the RKHS HNTK associated with NTK. By combining Lemma 3.1 with the well-known Mercer's 's representation theorem (e.g.. Theorem 4.51 in [33 we derive the following lemma, which describes the relationship between HINTK and HNTK-
Lemma 4.1, Fix any a 2 and D E N and define the corresponding TNTK as kYNTK gd-1 x gd-1 + R. Let kXTK _d-1 x S - R be an NIK corresponding to a ReLU-based L-layer neural network structure, where is any natural number. Then, HINTK C HNTK holds, where HNTK and HTNTK are RKHSs corresponding to kNTK and kYNTK, respectively.
The proof of Lemma 4.1 is provided in Appendix D Lemma 4.1 lidicates that the regret upper bound of ST-UCB is guaranteed in more constrained hypothesis space compared to NN-UCB. While
NN-UCB generally does not guarantee a no-regret property, the O(VT) guarantee in ST-UCB can be interpreted as being due to focusing on a more constrained hypothesis space.
It 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 221: however, we conjecture that by using more non-smooth soft decision function, although the regret may degrade to 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.
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 e-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 [. 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 S 768 arms, where K is a hyperparameter. The inputs are denoted as x - .) E X, where Bruilding
K-ddimensional one-hot vector used to identify the arms, and E is vector that aggregates the eight types of context. In most real-world data, the rewards depend not only on the observable context z but also on other information. To account for arm-specific characteristics that cannot be represented by ã alone, use Truilding as part of the input.
We consider each arm of the we define the reward of the arm selected in each round as f: - -(HL, + CL.). Additionally, we standardize the rewards across K arms to have a mean of 0 and standard deviation of 1.
bandit problem as an individual residential building, and
Synthetic dataset. We evaluate the algorithms using synthetic data similar to that used 41 Here, the number of arms is set to 20, and the dimension of the input vector æ for each arm is set to 50. Additionally, the input vectors are chosen uniformly random from the unit ball. We consider the three reward functions: (i) (x) 10(x a)², (ii) (() = x A Ax, and (iii) f cas a) where a E R550 is randomly generated from uniform distribution over unit ball, and each entry of A E R50x50 is randomly generated from standard normal distribution. Similar the real-world dataset, we standardize the rewards across all arms.
Setup. We define the cumulative regret up to round T as Rp = Er= E' where f* represents the maximum reward among all arms. We assume that the response used for training the machine learning model is generated from B ft + c, where e, is randomly drawn from normal distribution with mean and standard deviation nnoise = 0.2. Since the rewards are standardized, this setting of Jnoise effectively acts noise.
In this experiment, we will use an e-greedy based algorithm as an additional comparative method; In each round, an arm is selected randomly with probability of e, while the arm with the highest
8

---

122
1.6
Camutatti bogret
STng STigimatyy
STUCE
10
STADD preser crendy
Kil-grudyy
STigmedy
21
150
Aaund
Round
Round
K (real-world)
K 40 (real-world)
K (real-world)
260
Stuci
STura
STuCE
1de greedy
CumuBite Regree
15
Oar wor. Hogeet
grevyy
120
Stignoady
Stngnwdyy
57 Eigresdy
1.2
603
1.0
1aand
Roundd
(C0 (az)
a0
(
000
Coot
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 1 e. Here, we will perform grid search to choose the value of from the three candidates E (0.05, 0.1, 0.2]. Mean- while, in We use grid search to select the value of / from the three candidates B e (0.01,0.1,1},
algorithms, 3 is provided as a parameter to control the degree of exploration.
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 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 fixed at 10-4, regardless of the machine learning model. Supplementary details related to implementation of the algorithms are summarized in Appendix F.1
Results. The results for each algorithm are shown in Fig. 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 0g for the model. Additional results without the grid search for 6, 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 K = 60, after round 150, there was no change in the cumulative regret 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 e-greedy (NN-greed) 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. the (()) and f(2) settings of synthetic dataset, ST-UCB outperformed the other policies, and the convergence stability of cumulative regret in (3) was comparable between ST-UCB and NN-UCB.
6 Conclusion and future direction
In this paper, we propose new regret-minimizztion algorithm based on 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 ((VT) 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 a 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 fixed a, our proposed method is not guaranteed to maintain the no-regret property with varying scale parameter a. 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 crucial.
References
[1] UCI Machine Learning Repository - prrchiveiissuci.edee http://aacciie.iss...i.e.eee [Accessed 25-04-2024).
[2] Yasin Abbasi-Yadkori. Online learning for linearly parametrized control problems. 2013.
[3] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Proc. Neural Information Processing Systems (NeurIPS), 2011.
[4] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Proc. Neural Information Processing Systems (NeurIPS), 2019.
[5] Peter Auer. Using confidence bounds for exploitation-exxploraiio trade-offs. Journal of Machine Learning Research, 2002.
[6] Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. In Proc. International Conference on Learning Representations (ICLR), 2021.
[7] Ilija Bogunovic and Andreas Krause. Misspecified Gaussian process bandit optimization. In Proc. Neural Information Processing Systems (NeurIPS), 2021.
[8] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5). 2011.
[9] Daniele Calandriello, Alessandro Lazaric, and Michal Valko. Second-order kernel online convex optimization with adaptive sketching. In Proc. International Conference on Machine Learning
(ICMI.), 2017.
[10] Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Gaussian process optimization with adaptive sketching: Scalable and no regret. In Proc. Conference Learning Theory (COLT), 2019.
[11] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proc. International Conference on Machine Learning (ICML), 2017.
[12] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In Proc. Conference on Learning Theory (COLT), 2008
[13] Costas Efthimiou and Christopher Frye. Spherical harmonics in p dimensions. World Scientific, 2014.
[14] Adam Elmachtoub, Ryan McNellis, Sechan Oh, and Marek Petrik. A practical method for solving contextual bandit problems using decision trees. In Conference on Uncertainty in Artificial Intelligence (UAI), 2017.
[15] Raphaël Féraud, Robin Allesiardo, Tanguy Urvoy, and Fabrice Clérot. Random forest for the contextual bandit problem. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2016.
[16) Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint 1233 2023.
10

---

[17] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2010.
[18] Hussein Hazimeh, Natalia Ponomareva, Petros Mol, Zhenyu Tan, and Rahul Mazumder. The tree ensemble layer: Differentiability meets conditional computation. In Proc. International Conference Muchine Leurning (ICML), 2020.
[19] Arthur Jacot, Franck Gabriel, and Clément Hongler. generalization in neural networks. Proc. Neural Information Processing Systems (NeurIPS), 31, 2018.
Neural tangent kernel: Convergence and
[20] Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur. Gaus- sian processes and kernel methods: review on connections and equivalences. arXiv preprint arXiv:1807.02582, 2018.
[21] Ryuichi Kanoh and Mahito Sugiyama. A neural tangent kernel perspective of infinite tree ensembles. In Proc. International Conference on Learning Representations (ICIR)), 2021.
[22] Ryuichi Kanoh and Mahito Sugiyama. Analyzing tree architectures ensembles via neural tangent kernel. In Proc. International Conference on Learning Representutions (ICLR), 2022.
[23] Parnian Kassraie and Andreas Krause. Neural contextual bandits without regret. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
[24] Parnian Kassraie, Andreas Krause, and Ilija Bogunovic. Graph neural network bandits. In Proc. Neural Information Processing Systems (NeurIPS), December 2022.
[25] Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Bulo. Deep neural decision forests. In Proceedings of the IEEE international conference on computer vision, 2015.
[26] Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
[27] Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. Proc. Neural Information Processing Systems (NeurIPS), 2020.
[28] Sergei Popov, Stanislav Morozov, and Artem Babenko. Neural oblivious decision ensembles for deep learning on tabular data. Proc. International Conference on Learning Representations (ICLR), 2020.
[29] Sayak Ray Chowdhury and Aditya Gopalan. Bayesian optimization under heavy-tailed payoffs. In Proc. Neural Information Processing Systems (NeurIPS), 2019.
[30] Sudeep Salgia. Provably and practically efficient neural contextual bandits. In Proc. Interna- tional Conference on Machine Learning (ICML), 2023.
[31] Meyer Scetbon and 7aid Harchaoui. A spectral analysis of dot-product kernels. In Proc. International Conference on Artificial Intelligence and Statisties (AISTATS), 2021.
[32] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. International Conference on Machine Learning (ICML), 2010.
[33] Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.
[34] Athanasios Tsanas and Angeliki Xifara. Accurate quantitative estimation of energy performance of residential buildings using statistical machine learning tools. Energy and buildings, 49: 560-567, 2012.
[35] Sattar Vakili, Michael Bromberg, Jezabel Garcia, Da-shan Shiu, and Alberto Bernacchia. Uniform generalization bounds for overparameterized neural networks. arXiv preprint arXiv:2109.06099, 2021.
11

---

[36] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in Gaussian process bandits. In Proc. International Conference Artificial Intelligence and Statistics (AISTATS), 2021.
[37] Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. Conference on Uncertainty Artificial Intelligence (UAI), 2013.
[38] Hastagiri P Vanchinathan, Isidor Nikolie, Fabio De Bona, and Andreas Krause. Explore- exploit in top-n recommender systems via Gaussian processes. In Proceedings of the 8th ACM Conference Recommender systems, 2014.
[39] Roman Vershynin. High-ddimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[40] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural Thompson sampling. In Proc. International Conference on Learning Representations (ICLR), 2021.
[41] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In Proc. International Conference on Machine Learning (ICML), 2020.
12

---

A Information gain of TNTK
A.1 Proof of Lemma 3.1
Firstly, we formally define the dot product kernel on the sphere.
Definition A.1 (Dot product kemeel on the sphere [3I)). Let d 2 2 and S be the unit sphere of R. Then, a kernel k : gd x gd-1 + R. of the following form is called dot product kernel on the sphere gd-1;
k(x, x)) Σ ba Tz)" for all az x E ES" St-1
(13)
where (ba)nEN is an absolutely summable sequence. Furthermore, if bn 2 for any n E N, k is continuous positive semi-definite kernel on the sphere Sd-1
As described in Sec. 2 in [31] continuous positive semi-definite dot dot-product kernlls are decomposed as Eq. (6) by using spherical harmonics (Yn.)).
The following lemma shows the eigendecay of dot product kernels depending on coefficients (ba) (Na) Lemma A.1 (Proposition 2.3 in (T) Lel d 2 and (Yng) be the spherical harmonics of degree n. Furthermore, let k(x = ba( z)" be continuous positive semi-definite dot product kernel on Sd-1, Here, if there exist r E (0, 1) and > 0 such that by S cr holds for any N. then, there exists constant C > and (An)nEN such that Xn Cr" and k(x, .) Ex Nár An (n))n())))))))))) (n)) hold for all æ, E E S 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.I
Proof of Lemma 3.7
First, we respectively define functions fi [-1,1] + IR and f2 [-1,
as
a²a
fa(a) 2x
arcsin
(14)
a22 0.5
4
fe(a) = a²
1
(15)
(1+2aa2 4a
Then, since x, I gd-1, the following holds directly from the analytical expression of TNTK 21
KTNTK 2) DDx T () P-1 x) + 2 fi a)P.
(16)
Here, since -1
a²a a240.5
1 holds for any [-1, 1].
1 aresin
a²a
+ 1
fi(a)
(17)
2m
a² + 0.5
1
(2n)!
a
2x+1
a 2n+1
(18)
2m
(2n) + 1)
a
0.5
from the Maclaurin series expansion of the inverse sine function.
Furthermore, since 1 <
a 1+20
holds holds for any E [-1,1]
<
a² f2(a) V(1 (1 + 20 )- 4a 2
(19)
a²
(20)
TT + 2a
2
2a
1+2a
a²
-0.5)
a²
Σ
-11"
22n
(21)
7T1 + 2a
n
a
0.5
n=0
13

---

In= (i) am holds for any and
where the last line follows from the fact that (1+x)
E 1). Here,
denotes a generalized binomial coefficient, which is defined as
n 0: otherwise,
dic (cc-)).(ce-n1]] By rearranging Eq. (88) and Eq. (1 fi and fa can
m2
respectively be rewritten fi(a) Di=l D1 and f2(a) Ei= D where the coefficients
and are defined as
i 0, 3n E N, i= 2n 3m-11 1,
(22)
[2x
1//211²
@
otherwise,
if 0,
x(L+2a=
(((2)
2
2
1.5
0.51 10.5...0.5--- 0.51 1)]
if 3n E N, 2n, otherwise.
(23)
x[1+2a-]
40.3
[8/2]T
From the Stirling's inequality: e(n/e)" S n! S en(n/e)", for any such that 2n + holds, (2m)! (2m)22n (2n + ()
(i (1-1)! 1)!
(24)
((() ()()))))2
2en cem(2n/ee² )mn
(25)
(2 22m (2n + 1)e² (m/e)2n
2n
(26)
(2 (2n + 1)e
(27)
(2T)e
17
(28)
Therefore, 05
S <e- ( a²
holds for any E N. Furthermore, for any such that i 2n
(=40..)
holds,
a²
[0.5 1.5 (0.5 + 0.5i 1)]
(29)
TT1 + 2) (i/2)!
a²
(0.5 1.5... -0.5 + 1)]
(30)
7T1 + 2a n!
a
(1.2... n)
(31)
(1 + 2a²) n!
a²
(32)
π (1 + 2a²)
Therefore, 0 0122)
2
2
holds for any E N. Now, rewrite Eq.
16 by using
+0.5
the multiple Cauchy product formula as follows:
KTNTK (x, .t) =
Σ
ba xt);
(33)
1=0
where,
DD
Σ
(1)
(2)
12 0g 0=00
=0
(34)
i $ Σ
+2D
11)
(1)
==
i0-1=0
14

---

By combining Eq.
34
with the upper bounds of (,0) and 6,()
D-1
a
a²
in
b. S D
Σ
Σ1
(1 +
2a²)
a²2
0.5
iD-1=0ip= ip=
(35)
1
D
a
1D
10-2
iD-1
+ 2DD
Σ
Σ1 1 1m-1=0 ip=0
Σ
8
+ 0.5
12
D-1
a²
a
ID
1 D
a²
i
2
(i - 1) 11-1)
+2
1
(36)
a(1 + 2a
a2 0.5
a
+ 0.5
D-1
a
α
iD
D
+2D
(37)
T1 + 2a.)
a
0.5
Therefore, there exist constant Co.D 0 such that
a²
iD
h; S C.
(38)
a +
0.25
holds for any i E N. By applying Lemma
A.1 with Eq.
(38
have
a²
iD
(()) 02D
A S
(39)
02 + 0.25
a
a,D exp
iDIn
(40)
a + 0.25
= c(I)
a.D exp
-iDIn
1+ 4a
(41)
for some constant (
A.2 Proof of Theorem
Our proof strategy of Theorem 3.1 is adapted from 23 35
Proof of Theorem 3.7
Fix any deterministic sequence FI....,
24 E X Sd-1, For any M E N+,
let us define kernel functions KYNTK and K
Na.
A (M) TNTK (0,
X (x)
(42)
Na An Yn (2))
((M) KTNTK (x,
(43)
Furthermore, let K (M) TNTK and Kc
(MM) TNTT be t-kernel matrices whose (i. entry are (MM) (æ; 2④)
and RMM) (æ;, mz), respectively. As with the proof of Theorem 3 in 36), we have the following decomposition:
In dot + (INNKKK
2
(44)
1
In det
1 p
(M) KTNTK)
+ det (1+ p-
(I++p' 1 -
K
K
TNTK
(M)
2
By following the same argument the proof of Theorem in 33 the first term of Eq. bounded from above as follows:
44 is
det (I, 11+pp=
(M)
NM In 1
Tel
(45)
2
2
P.a
15

---

where Na MM Na, and & = maX (x, x). Furthermore, by following the same
argument the proof of Theorem 3.2 in [23]. the second term of Eq. (4) bounded from above as follows:
2
det
Ietp-
11--p1 )
KNNKK
R-(M))
TNTK
(46)
t in
p
pr
KNNTKK
1
(47)
2
t
In
1+p-
Σ Ndn
(48)
2
n=M+1
t
Nd
(49)
2p
Then, from Lemma 3.1
there exists some constants C > O and Ca,d > 0 such that
8
Σ
Nd S
Σ
( Cepp (-Ca
(50)
T= [=M+] M1
==M+1
8
(51)
n= M+1
where we set Co C. = In(1 + 1/(4a))), Furthermore, Eq. (see, e.g., (23 Therefore,
50
follows from Na.. O(n
Nd I CaDDCCa. 1 exp (=0.5.., dr
(52)
JM
A== M+1
C.DM
Ca,DDeee
(53)
2
where set Ca, Da, = the constant Ö > 0 such that
a, Cap CC
Now, by noting NM O(M--1) 23 there exists
NM In
Ttt
m
In dot (Ie + (INTK) s
-I+pp-KINIK
1+
Σ
An NdN
(54)
PN
2p
n=M+1
dMd-1
Tot
Ča.D.at
C.DM
2 In
1+
exp
(55)
2p
2
By choosing M as
(a.
(
M
2C DD- In
In
1+
(56)
16

---

M3 2 1 for sufficiently large t. and we have
M
2 In
--- Ca.D.alp-10 10-1
In (1 1+ p
)
ki
(57)
1 ktt
+ M 2 20-
In
(58)
C.DM
Tot
+ exp
Ca.Daat
10-1
In
1 1+
(59)
2
1+ ht
C.DM
+ 11 12 D, 10-1
exp
(60)
2
kl.
C.DM
7 M 2 Ca,Datt -
-
In
1
exp
(61)
2
ČMa-1
lot
Ca.
C.DM
In
1+
2
exp
(62)
p
2p
Therefore,
In dot (I, + p - -KKNTK
(63)
1+ kt
ČM In
(64)
P
1+ Tot p )
1+ let
< 20-1D--1m In
Ca. in
Ö'n
(65)
= In t).
(66)
The above inequality holds for any choice of Rr; hence, the proof is completed.
B Confidence bounds of soft trees
B.1 Proof of Lemma 3.2
To prevent the subscript from becoming redundant hereafter, unless specifically stated otherwise, denote the initial parameter 0g by := Og and the initial parameters of the m-th tree are denoted by Moreover, the initial parameter vectors corresponding to the internal nodes and leaf nodes for 0 (m) are denoted by (m) and π (m)) respectively. First, following 21 we decompose the finite
sample approximation of the TNTK as follows:
(V Nxx; 0o), Vo, (á: 0o))
(67)
mimo. mo
(x: (e:))mm)) V (mm ( 0(m))
(68)
M
1
xx: ol()))
( m(m)))
M
(69)
M
2a Me (m))
iz; m(m))
M
m=l
M
V (1() (m))
x (e:)(()) v (m
(x: mm))
(70)
M
mm
17

---

Here, (m))((2) (m)) and (()).(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 the initial values, respectively. Now, we define KTNTK (2, T), KTNTK( (x, Z), kTNTK (a,, T), and T (2, x)
follows:
TNTT x x) E
(m))cr) (m)
0 (m)
(ryhh (m)
( (m)
(71)
10
TNNTK (x, x)) E
(LL))
(mm).c (m)
mm0m) (m)
V
a;; mm))
(72)
FINTK (2, .) E
((B)
( (m)
ax; 0 mm)
mm)) (m))
(73)
KTNTK (2) E
( (V (m))
<x; 0 (m))
mim) h (m)
)
(74)
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 parame- ters follow multivariate normal distribution independent across dimensions, by using the law of large numbers, Eqs. (68), (69), and (70) converge probability, respectively, to kYNTK (az @), (LL FINTK (z. .)) + FTNTK (z. T), and KINTK (2, From the continuous mapping theorem, it fol- (L)
(R)
(B)
lows that kTNTK (z, ④) KTNTK(# (a, t) + kTNTK (ac, 2)) + kTNTK .) + KTNTK (xx Ø) can be expressed (2]. Note that the convergence the above TNTK also holds for the initialization strategy of ST-UCB. Actually, regarding Eq. (68), we have
1
(2:; (6(m)(m)
(m(m)),))))()))) (
(x:00)) ((m))
(75)
M
M/2
(r (z; (
2
.M
m=1
M/2
M// h1 (2:0fM/2+mm)
mo) (mm)
(#: 02 M
))}-
m=1
(76)
The first and second terms correspond the inner products of gradients when initializing M/2 /222 soft trees with the standard normal distribution and converge in probability to KTNTH (x. There- fore, by the continuous mapping theorem, Eq. (5) converges in probability to x(T) (ax, m). ((P)
(B) Similar arguments apply to kTNTK (x. σ) KTNTK (xx σ) and kINTK (x, æ), indicating that in the initialization strategy of ST-UCB, h(x; Bo), Ve, (æ:; 0o)) also converges in probability
k (L)
to (I,TK(œ, Ø). The following three lemmas each evaluate the concentration to A: (x, Ø),,
LLL) KINTK (x, .) + I (z, .), and k (ax, .)) for Eqs. 68
669 and (70). respectively.
Lemma B.1. For any x, v E gd-1 and 0, we have
P N WENTK (2,
Σ
(r)
(z:)((")) V (nnm),er,))
(x: (ā:ef(m) alm"))) Se
m==
2 c
2 1 - 4exp
-cminn
M).
K2
K
(77)
where K = C22 Furthermore, C, e > O are absolute constants.
18

---

Lemma B.2. For any 2, 2 E gd-1
c O, and D N 2, we have
M
x; (=:))/")) V Varmrosh (a::fm))) Sc
KINTK ( x)
M
m==
e²
2 11- 4exp
-cmin
M
K2
K
(78)
Furthermore, we have
M
P
((R) (
(2,
Σ
(V
(n) ((m) (x; (x;0, m5m)))).
Warms.c (m))
( (f) Se
M
m=
e² c
2 1 - 4exp
-emin
M1
K2
K
(79)
Lemma B.3, For any x, i E gd-1 and & 2 O, we have
M
P 1INTK(2, (x,
Trimi (m) (x; 00:00 00m))
mim) (m))
(x: 0 (m))
S(
(80)
CE2M M
2 21-
C
Here, E> O is an absolute constant.
In proving the above lemmas, following [1], we denote a single soft tree of depth D determined by
the internal node parameters Rd2 1)) and leaf node parameters E IR2 h w, πτ)
Proof of Lemma B. Fix any D < D, E Rd)2--1), and E R From the definition of the soft
tree, the following recursive formula holds [2I]:
h (2r, w.
=0 (w 21) 1 x (()) n xl)) + -o (w((T x) h/ (z,, (R) π (1)).
(81)
Note that h(m)((z ((m)) hD (x, wim), r( (m))). Here, T(4) n (1) represent the parameters of the leaves belonging to the left and right subtrees, respectively. From Eq. (8T), we have
( w, π)) æv (T( x) [iD_1 (z, w (1) h (2, (n) ग ( (82)
where (b)
v is the derivative of (-)). Therefore,
(V (win (x, w, T,, V m h (it w. w)
= T (T) x:) (T))
| (x, (x. w((), ;0, x1(1) 1 (ar w((() π x((1)
- -ho-1
x (() T (1)
h
à (R) (R)
(83)
-hp-1
x ( (1)
h h
④ w(() π (()
+ 11
c w
n
R2)
h
c w (1) (2)
Here, let us define Pp. (z, w)
-
(w
lun [1 - o (w (T]T æ)
the weight proba-
bility function of leaf / in soft tree of depth D; then, we have
20-1
h (x, w(() x
Σ
mi PD-1. (2, (0.))
(84)
1-1
19

---

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 E [MV] we have
2
h (z, (L)), T )1
(m)
xx tolm).
m
PD-13
(85)
20
Σ
(86)
1=1
CL
(87)
where the first inequality follows from pD- -r- 1. 2; w (m))
1. Similarly,
hD- (x, (lm),( {
- CC. )
(88)
Due to oo S IT, x σ s 1, and Lemma E.4 we obtain
\ ( (x; (m)) mery ((m)
a 0 (lm))))
))m
4C
(89)
From the centering lemma (Lemmal
E.3 there exists an absolute constant
Ö > 0 such that
1 COc2
ATRTK (x. x) - (V Wirr x ())
V w! (z:00 0 (/mm")))
(90)
S 400 caa
(91)
Therefore, taking CC2 new absolute constant C and using the independence of parameters for each E [M/2], the application of Bernstein's 's inequality (Lemma E.2 yields
M/2
P
he (x, Φ)-
2
Σ
V
(rm
xz; (e:)) v cry
(#: (e..omm))
2
M
17
e²
(-emin
<
2exp
M
2K
2K
(92)
Note that the similar inequality also holds for m E [M] \ [M/2]:
M
F (TT) (2, a))
Σ
mmmms.eryh (m)) xx: (e:))!)) V (0mm (æ; omm)) 2e
M
M/+11
2
< 2exp
-emin
M
2K
2K
(93)
By taking union bound in Eqs. the desired result.
992 and
93
and taking c/2 as an new absolute constant c, we obtain
Proof of Lemma B.2 We only show Eq. 788 for simplicity. Fix any E R&V and R corresponding to the parameters of soft tree depth D. Furthermore, let w;; and n& I W) 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 breadth-first
order, hence by definition, W2. = ( W3: = (R)). From Eq. (8I), we have:
Polcy w. π) =a (T) x vwccsho-11 (xe (1))), (1)).
(94)
20

---

Given that ((o()))lc I 1, for any m E [M], we have:
K V (mtm (a: (m:)) V Weotmrcesh (æ: ))
11
Mim.suup (0 ml)) xlm)(ti) wam (i, w (m)(())) - (m))
(95)
Now, decomposing the gradient of the subtree rooted at the left child of the root node, we have:
V (o ( (2, (z) π (1)))) ww (ē, w((,, π )
(96)
V wn. hD- (x. W2 T2:).
Vwy 1p-1 (ã, W2: T2:))
(97)
V in hm (z, W2: T2:)
(T) hD-1 (i, W2: T2:)
( hp- (Ø; W2:; T2: (2) h (x, W2: T2
(98)
+ (m) hp (x, W2 T2:)
( hp-1 (z) w2. T2:
Considering that W2: are parameters for soft tree with C/2 leaves, similar to the proof of Lemma B.1 there exists an absolute constant C' such that for any m E [M]:
Lommeer hp-1 (zr, W2z .2 m0
(I. (m)
(m)
V
(2, w ... (m)
)) |m, S
(C/22)
(99)
Similarly Eq. 955, we have:
ao xx, W (m)
2 {())) v
c (
(m) {(m)) )
41
m (1. w2 2:
(L) (m))ll))
V w Vog ( w (L) (m))((2)
(100)
Similarly, for the right subtree:
Lo (ar; (2r,w W2 TT.
[m] (m))
V
(m).
hD-1
(m) (m)
..
V1
(m) hp-2 W.
(z)
(m))
v 3
(i. / (
(m) (m),(1))
2:
(101)
Therefore,
K i mm..cc)) (x. (m))) x (m))))))))
Vomm). (ë, (m))) x (m))((())
< 4a Cm (C/222
[|( 2.
(L).LL)
((m))(()))
1 E w.y (L)
मे. (()))))))) )
x w. n2.
|| w h
xr, w n (m)).(1))
(M).(R)
1D ( w
(m) (m)).
(102)
By repeating the above described argument, we can further decompose the second and third term of Eq. (102) as follows:
21

---

|( ( (immaaaa (m) (
x(m);(t))
Vamm.chho- ( (() न. (
19
(103)
$ 4a Ca (C/2)
(104)
+ 2x 4a CT (C/4)²
(C/44)
(105)
W mm 1D-
w
8:
(m)
8:
(m)
V
mm
h
i 8:
mm)
8:
(m)
(106)
V
1D-3
2. 9:
9:
(mn) hp-3
à. w
9:
(m)
7 9:
(m)
(107)
(
(m)) hD-3
2, w
10:
(m)
[(m)
10:
[m]
21 10:
m)
π 10:
(m)
(108)
10:
mm)
e 11: - (m)
(m)
hp-3
m)
11: 11:
(m)
(109)
By recursively applying the above discussion until reaching the leaves of the tree, we find:
(k w win).tt) (o- (xr,0((m))1)) (m)))) (())(()) V Wwtt (ir w (m))(()) π (m))(()))
( C
C + .... 2 x 4a²
C 2
< Cx -1
+2x C0
2
4
2D-1
(110)
Thus, we conclude:
(1) (c:))
(111)
4a²0
D-1
2 C2
(112)
22
2a CLL D-11
2-
(113)
i=1
2a C02
(114)
C2
(115)
K.
(116)
Finally, by applying centering lemma (Lemma D33 Bernstein's 's inequality (Lemma and the union bound, we obtain the desired result.
Proof of Lemma B.3 From the definition of (m), we have:
((m)
ar; (5:(((m) = (ps (2;; mm(m))
,. PP rr; mmm)))
(117)
Noting that |pt (x:; w)l 5 1, we have:
( (m)) (e:e((m))
V Vatma (m)) xx: (x:0(( (lbm)))
pi x w (m))
2
(118)
< CL.
(119)
Therefore, by applying the centering lemma (Lemma E.3 and the general Hoeffding's inequality with union bounds, the desired result is obtained.
(Lemma E.T
Lemma 3.2 is derived by taking union bound over the three preceding lemmas and rearranging the
entire expression.
22

---

Proof of Lemma 3.2
Fix any
such that E < K. Then, min
{
2
2²
Now,
R²
K)
K2
K²
16
8
M
+
4exp
M
2
(120)
o²2
R2
4'
C2
16
8
M
In
exp
(121)
ćc
L
4
Therefore, from Lemma B.1 Lemma
B.2
and Lemma
B.3
by applying the union bound,
K²
L
16
M max
In
(122)
5
PP ( (xr, (x, a)
(g 0o). g 0o)) S 4e) 2 1 1 5.
(123)
Finally, let = max (1/c, max 1/2), then
16
M max
c c²2
(124)
5
K2
L
16
M max
2 In
(125)
c
8
By defining D.D. aD = K, the desired result is obtained.
B.2 Proof of Lemma
Proof seketch Since the parameters of the different soft trees independent, we can confirm that the Hessian (x: 0) 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.
Proof of Lemma 3.3 Define (mm) (1c, ((m)))
V gim (mm) (æ; ((m)) E RXxY where p - dN+C.
Then, H f) is represented by the following block diagonal matrix:
H (1) (x, 0())
Dxp ax. ((1)
Opxp
Opxp
(
Opxp
H(x, 0) VM
1 (126)
( (z,, 0(()))
0 Oxxp
Opxp
where Opxp represents a x p zero matrix. Therefore,
H (x, 0)1
max mE[M]
Hm x. olm))
(127)
VM
Here, assume the following event holds:
Vm E [M], vI E [4], Vn E [M],
I 2 In 2M(++N) and w (m)
2M +N)
(128)
S
2 In
Since On initialized standard normal distribution, by the union bound, the above event occurs with probability at least - 8. Therefore, it sufficient to show that Eq. (TT) holds under the event
128
Now, the derivatives of h (m) (x; ((m)
up to the second order are given by:
2 (m)
(x:; (())
(m) Ppi(;; (())))
Ow. (m)
ow (m)
πi
Sw dw (m))
(129)
( (m)
xx: (m)
apr(æ; (m)))
(130)
Ow [m]
mm (m)
Own (m)
(2h(m))
(x; (m)
O.
(131)
3m
(m))))
(m)
mm (m)
23

---

From the definition of pt. we have
Opr (a:; mm)
(wo(m)T x)
Il _ (wof (m)) xt
Own (m)
(132)
////
a II n
un
(m))
x.)
ur
(m)) m3)
dd Pi (z;; w(())
I/ xx
To (2))"
(m) x
- nn Snaw Tō ! (mm) x)
(m Oron (m
(133)
II a 2
(Tr)
x))
[ - (
(m))
x
0² pi (z; w(m) @rm (m))
1 n (wo(m)) x))
1I 1 (an(m)T x:)
11 nard
(10 (ofmm)T
1 L
(m)m)) (m))T x
(134)
Diva
lave
x
(m))T 2
-
(m)T
x))
In the third equation, it was assumed that n. * â. Now, let us evaluate the upper bound of the above expressions. First, from the definition of (-)), we know that [l)(())) I 1 and [|x()) a/ vTr
Additionally, for any a E R, [ā(a]] < 2/a|a" 2 /VT. Then,
PP (z; (m) @w!!! (m) Dron
w
(m) (m))
x
/
In I
||
(135)
a²
5 2
w
n
m2)
x
xx
||
(136)
a²
$ 2
w n1
(m) x
w
n
Tm)
x
+
w
(m) x)
V
||
(137)
2M
N
2
S 2
+
1 21n
(138)
VT
Furthermore, as for n * f
00pp(x; w (m))
(139)
Owlli (m) Iro (m))
(w)m)) x3)
x:
1
(140)
20 (m)
(m))
1
x
B I no
x
w
T
x
xx
In L I 1
x
w
(ma)
x
xx
I1 1 1i
2n (m))
2x)
w
n
(m))
xx
+ la La yiō
(1) (m))
x
mn
(mm)
x
F
(141)
x [|ā(-)) 12 1x I|F
(142)
2
(143)
24

---

Moreover, we have
@2((m) (x;; 0lm))
pr (x; w w()))
[m) T
(144)
Own (m) Ow (m)
(m)
F
8 Di (x); mm)
+ | [(m)
(145)
Ow (TT)) gro (m)
2M + +m))
PPi (x; mm)
R + / 22
(146)
8
twm! (m) gro (m)
Therefore.
2
(m)
(147)
H (m)
(mm)
2. 0l())
|
(148)
N
g2 (ac: (l))
(P (æ:; 0 (mm)
Owen ((m) Our Bur (m)
Ownn (m) Om, (m)
F
F
(149)
(m)
(a:; O(m))
Om (m)) am (m))
i=1
8 hi
(x;; ((m)))
2
(1 (x;; O(m))
NV
(2
(x:; ((m))
+
Dron Oron. (m)
Ownn (m) Ow (m)
(m Om (m)
(m)
F
ne
F
(150)
N
2M + NN
O2 pt (x; (m))
R+
12
Own (m)
Owo (m)
2
(M + W
p' (x;; ue (m))
R+ V 21n
(151)
8
Owa (m) Ow (m)
nyn
Opi (x; w (m))
Own (m))
n=1
N
< Σ 4
R+ 21n
NM
a
+ Σ L
R /
21n
2M + +N)
a
6
8
n=1
nzn
(152)
+ 2 a²
R+ 2ln 2M +N
a + -N a²
S <
(153)
π
(M(++N)
<2
R+ 2ln
a² + 2N2c2a'
(154)
2M
S 62
R
21n
(155)
where:
. Eq. 150
follows from Eq.
131
. Eq.
151
follows from Eqs.
146 and
130
25

---

The first and second term of Eq. 152 follows from Eq. 143 spectively. Furthermore, the third term of Eq. (152) follows from
and Eq. 138
re-
Opi (m))(())
Owh (7)
P
Wn (
2) ln Iav (w (T) x
- 100( S vे.
Eq. 154
follows from 1/Tr I and a 2 1.
Eq.
155
follows from R- - v 2 2M(C+N)
2 (V21n2)* 2 1.
By combining Eq.
155
with Eq. 127 we have
2
VBa2NC
2M
+
H 0)1 &
R+ 21n
(156)
VM
5
2
V6a222D
2M W
R
21n
(157)
VM
5
Finally, from the definition of C(3)
a.D=
V6a2220 (R v2)² ((3) C V22
(158)
2
22
R
+ V2 v3]
<0 C (R+ v2)
(159)
2M(C+N)
22D
2ln 2M([+N
((3) (R + v2
2M N
R+ +
(160)
VM
VM
22D
2M + M)
((3)
2)
2D2
R+
2
In
(161)
VM
VM
where Eq. 159
follows from (N + L)/8) > In 6 > 1. Furthermore, Eq. [66] follows from By combining Eq. (161) with Eq. [17].. we obtain the desired result.
L+N
2D
B.3 Proof of Theorem 3.2
Instead of showing Theorem 3.2 directly, we show the proof of the following detailed version of Theorem 32
Theorem B.1 (Detailed version of Theorem 3.2). Suppose that Assumption 3.7 holds. Fix any ò E 1), 2 1, > 0, and D > 2. Furthermore, suppose that the number of ensemble M is sufficiently large to satisfy the following four conditions:
ln 1
M 64C
1212
(162)
16
M (6) (2)-2
(163)
0.D
3n7 Mp
12T
6 D+2
M
i + 2)
<
kB + v
2ln
In
(164)
(3C
8
((7)
a.D.T
kB /
2
127'
[n
6 2D22 M
In
6M
< 1,
(165)
VM
8
8
26

---

where:
R=
(2R +RR+2% 22)
>
TC 0,
6M
BB + +B++V22
2
12T
V3T R
(166)
2p
12T 2ln
T
2= kB HtB+oy
(167)
8
Then, if the learning rate yj satisfy nj S 4-1 (p+ 2(2R + 2 TT In
0,
6M 8
with probability
at least 1 - 6, the following inequality holds for any t E [T] and x E N:
72T C(1) 0DD
12T
3-2 2
[f(x) - h1:;; 0r1))
BB + V 2
In
+ 10t- (168)
5
where:
T
TCL. |n(96).212/0
3 == V2B + a
2
rr +
In
VP
PVM
8
(C(7)
2
+ p 1-VE VV= + 4C
a.D.T
TB + o
21n
12T
In
6 6-2
In
6M
(169)
0.D
VM
8
+ (1 - 2mpp)
kB + V
2
12T
T
0,D P (C(()
(4) 22D 82 In
20
6M
8
Here, C 0 and Ò > are absolute constants. Furthermore, c( 0, c 0, and ((6) constants that depend on and D. Moreover, Te == maXzEX v VKTNTK (x, x)) is the square root of the maximum value of TNTK, and c!?) a,D,r = =O(T3) is the constant that depends on a, D, and T
B.3.1 Proof overview
In this section, we briefly summarize the overview of our proof. We first define the following six events:
(33 (R+2)
6.22-2M M
V0, x, R, 0 - 0ol12 < R + H (x. 0)1 <
In
VM
E
Y0, x. R. 0 00l12 < R (g 0) < c((. C (2R 32R+220)) 2T)) In 6M
8
0 n²a
E3
v0, R, 1 00l12 s R + ||g(;; 0) g cc; 0n)113 <
In 6M
.
E
127 vt (T), 11 < [B. + 2n
5
v
E5
Va, &. |KTNTK( xt) k(xx, 3:) < min
Ao 2
10 0.0
In 2112 (2
Ad
0.D
E6 = Vt N4, Vx E X, x,11(z) (--1(()) < (V2B + vo
V 2( + In !) ā (
The quantities k; (.(4) (((5 (6) Āt-1. k. and 5y are defined in Lemma 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 &a simultaneously holds with probability at least 8 for sufficiently large M by taking union bound; therefore, it enough to show Eq. (168) under the event [iejo] E, Hereafter, show Theorem B.I in the following steps:
27

---

Based on the above decomposition, we derive the upper bound of each term under the event Aseea & with sufficiently large M. The first term of the above inequality is bounded from above by combining the event &g with Lemma B.12 The second term is bounded by resorting to the arguments from [1), which is based on the optimization error of the gradient descent of the linearized squared loss (Lemma B.9 and Lemma B.IT). The upper 1. For sufficiently large M, we show that each of the events &g n & and & holds with probability least 1 6/6 in Lemma B.4 Lemma B.5 and Lemma B.6, respectively. Furthermore, as shown in Lemma B.7 the event & holds with probability at least 8/3. Since we already know the event & holds with probability least 8/6 from Lemma 3.3 we can show IP (Nieee) E,) 2
in this step by applying the union bound.
2. As with the proof of Salgia [30], the error term ff(x) h( 0:) is decomposed as follows:
If(x) h(x;
< [f(x) - -+((=)] + (p(())) (g(x; 0o), 0, - -bu) + [g(((; 0, - -0u) - h(x;; 0e)l-
(170)
bound of the third term is obtained by combining the event & with the fact that the error of the first-order Taylor approximation can be characterized by the spectral norm of the Hessian.
B.3.2 Lemmas for the events Eg-Es
Lemma B.4 (Gradient norm bounds). Let (0, M 3, and 2 1. Furthermore, let Og be initial parameter of ST-UCB. Then, with probability at least 1 for any x E Sd-1, R 2 0, and RP such that l 0ull2 $ R, we have
1)(3;0))1 S (2R (2 8
(171)
( RDDR M
[g 0) g(;; 0o)
In
(172)
M 5
where > 0 is an absolute constant. Moreover, c_. 2D and (.3) = =7 -3. Ca?
Proof. Suppose there exists u 2 1 such that the following event holds:
Vm
[M]
(m) u.
(173)
t=1
Following the proof of Lemma 8 in (1], we can derive that:
lgg æ: 0) < SN a) + c,
(174)
g <z; 0)
((:; 0
(175)
M N
N
2
Σ
(m)
-/ (m)
+ 200
w
(m)
(m))
||2
(176)
M
m= n=1
-=1
7=1
N
2
|| (w(()))
W m)
11/2
(177)
[ml
n=1
28

---

Furthermore, in the second inequality, we obtain the following upper bound from the Schwarz's inequality:
N
2
M
1
Σ
a
(m)
#1
(m))
+
2004
|
(m)
w (omm)11
112
(178)
1=1
N
2
(m))
fm)
un! (mm)) 112
(179)
[=1
M
N
2a CII (m) - क (m) + 4a22u2
(20 (m)) 2 (m) 12
(180)
M
m==1
L==1
C
N M (m)
w m
(181)
M
Σ
N (2a2 + 4a uu2 + C) (10(()) -0"m! 1
(182)
M m=1
N (2a2L C + uNN + +2) 0--02
(183)
M
R
(184)
M
Here, using the general Hoeffding's inequality (Lemma H.T and the union bound, the event (173)
holds with probability at least 1 - 8 when u = VCCI(MM/8), where Ó' 2 1 is an absolute constant. Therefore, with probability at least 1 5:
M
19(0; 0113 N R+ V
a² + C,
(185)
(,65 12 R2 M
11 0) g(x; 0,)113
<
In
M
8
Finally, from the definition of ((0))
2 2 + LC) a² (2
(186)
2 (2R
2 = -... (2R LO2²
(187)
22R + LCPa2 2² +26 < (000 (2R - LOO²
(188)
N 22R++ LÕ
2
22 < ((4) (2R + LÕ)²
(189)
R
+ VLC
a +
L
(4)
(2R + LŌ)²
(190)
vhn
1n2
D.a
2
N
R
+
+VC
2
L
S ((01 C.a +
(2R L.1
(191)
Vin(M/5)
In(M/8)
M R+ v cC0n
a² + L 5 c(u) (2R+ LO) In M
+ N
(192)
g
where:
Eq. (88)
follows from (2R+ LZ)a2² 2 L since a 2 1, Ò 1, and R 2
Eq.
189
follows from N < 2D and LŌ > 1.
29

---

Eq. 190) follows from v 2 1n2 2 0.5.
Eq. 191 follows from the fact that In (n(M/6) 2 In holds under M 2 2.
Lemma B.5. Fix any ò E (0, 1) and f HTNTK with INIl S B. Furthermore, suppose that E is a o-sub-Gauss random variable for any t [2]. Then, with probability least 1 ö, the following inequality holds for any E [T]:
27 8
|l -
kB + 0 2
Vt.
(193)
where & = maX / /TTTTK(Z, x).
Proof.
From the reproducing property of RKHS and Schwarz's inequality, for any a E X, we have
f(x) = (ff, KTNTK(TK H)H
(194)
[[ [TTTTKTTK TTTNTK
(195)
= || / (x)
(196)
Bk.
(197)
Thus.
| 112
Iif(x)) + tzl i=1
(198)
Σ [B + lesl)
(199)
By using the concentration property o-sub-Gauss random variable, for any E [T] and 8 E (0, 1),
2 5
P E s v
2
2 21-8.
(200)
By setting 8 as 3 = 8/T and taking the union bound, we complete the proof.
Lemma B.6. Let 8 (0,1), D > 2, and X c gd-1, Furthermore, let KTNTK(X)
[WTNTK(R (ae,TK(E,0 a))x. E | and λo = Amin (KINI<A')) > 0 be kernel matrix over X' X and the minimum eigenvalue of KINTK(X) respectively. Moreover, assume that
a, 1x In 16
16|X
M 2 (4)
5 and M 2 C.2)
(201)
0.D
5
hold, where C.D.) Ö max C_222 22D) Here, Ò and C.?) are defined in Lemma 3.2 probability at least - 8, the following inequality holds for any x, x E X:
Then, with
4C(6)
[TTTTK(F .) k(x,, #) min
22
No
M
0.D
ln
4C(2) 16
a.D
(202)
where k(x,, .)- = (g(æ; 0o). (á; On))
Proof. From Lemma 3.2 and the union bound, for any e (0, c(22 D) have
M 2 (6) D In 16
5
(203)
P(Vx, & E X, 1KTNTK x) (g(2,, 00). g(t 0b0) < 45) 2 21-5
30

---

Here, we set as (0/
(n (n C. then, E E (0, C.D))
VO..
Therefore, by using Eq. (203). we have
-2
C a.D
(G) min
A
16
C((
16 21/
M
In
In
(204)
8|18
M
4C
7 P
Va, E E X, (IINTK(2,)))
k(2, xt1 $ mmin
Ao
a.D
ln
1
4C 0,
2
M
5
2 21-6 5.
(205)
Furthermore,
M 2 640 (6) aD 20= In
16 5
and M 2
(G)
a,
0,D In
(2)-2
16
c(
(206)
M 2 ((6 DD
Au
a.D
16
C(22
16
min
In
In
8|2
M
0,
By combining the above implication with Eq.
203 complete the proof.
Lemma B.7. Fix any E (0, 1) and f HINTK with [l S B. Let us define k as k(x 2) = (g(x; 0o), g 0o)). Furthermore, suppose that (CE),EN, are conditionally Sub-Gaussian random variables. Then, under the event &s, with probability at least 1 ò.
V E E Va E X, (f(x) (x=)1 S
12BB
2 5e +m o (2=)
1n
(207)
Vpl
Here, we respectively define (x)) and 7/o
(x(x) = ko (x)
Kr pI:) plo))
Ye
(208)
tt max In (I+ p- -K,) mi....
(209)
12 and K, [K(2,, (((,,,)))isss where (x(x)) = 1k( x J.llie (g(x: 0o). (z; 0o))
Rett with k( .) =
Proof. From the definition of Es, we have kTNTK (x, 3) (g( s. 0o) E 0o) S (2/(2| for any ar &. E X. Therefore, v Ex.eex kITTTK (ar, .) (g( 0o); g @.. 0n)) An/2. Here, by combining this inequality with the arguments of the proof of Lemma C.5 in 24 under the event &s. we have f E Hi with ||fll s /2B. Therefore, since ju, and o, 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 8 E (0, 1); then, P(Nie &,) 2 holds.
Proof. From Lemma 3.3 B.5 and B. we have P(E < 6/6 for any i E [5]/[2,3] 3). In addition, 8/6. Here, from Lemma B.6 and Lemma B.7 we have
from Lemma B.4 we have F(2E 3
P(EE)
P(gg (s)P((s) P(E (E))
(210)
(211)
6
(212)
3'
31

---

Therefore, by taking the union bound, we have
P() &)
(213)
[P(EE) + P P(E)) + +(())) + P(E
(214)
2 8.
(215)
B.4 Lemmas for the upper bounds of Eq. (170)
Definition B.I. Define (0) for any N4:
(.(0) || (0 (0) + 100122
(216)
Furthermore, let us define ..: 0..
Ous = -
{2G,
2Gr G. (0ng-1- y1 2p 10
(217)
where 02,0 = 00-
Lemma B.9 (Adapted from Lemma C.4 in Suppose that the events Eg and &g simultaneously
hold. Furthermore, assume that 2-1 TC2222 (1) ln(6M/0) + holds. Then, the
following inequalities hold for any E [T] and j E [J]:
|o - -0012= kB 1B+
12T
V/ 21n
(218)
8
|0:s 0 00 (pIp G.G.)
Giyil
< - 21p) kB + oV 21n
12T
V
(219)
where To defined Lemma B.5
Furthermore, the constants Ö and ((4) o.D are defined in Lemma B.4
Proof. From the definition of (0), have
VgL.(0) = -G,G. + 2pIp
(220)
x (IG.) + Ip
(221)
32 102220 (4) a
6M In
+ +P) Lp.
(222)
8
Therefore, (.) is 2 222222 ((u) In GM + p)- smooth function. Furthermore, (0) is 2p-strong convex because (O) > 2pIp 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 [66). (o 2 (.(00.)11) holds for any E [J]. Therefore,
where Eq. (222 follows from Lemma B.13
p 0 1 < G. (0.. 8o)
0 0
(223)
GT
(0ro - 0n) - yr
+ p
0. - 00
(224)
11
(225)
12T
kB a 2
(226)
5
where Eq. 226 follows from the event &,. Furthermore, since the unique minimum of (, is
given 0" 0o (pI, G.G.)) Giy.. have the following inequalities from Theorem 3.6
32

---

in 16
Giyt |
0ig 0. (plp + G.G..
(227)
$ (1 2mp) 100 - -0
(228)
Σ (1 2mp)
(((()) L, (00)
(229)
(0o)
$ (1 2mp)'
(230)
P
| 12
< (1 2
(231)
2 t kB + to
2 12T
$ (1 - 2mp)
(232)
P
where:
Eq. 229
follows from (i,(0") and the fact that L. is the 2p-strong convex function.
Eq.
230
follows from (0*) 2 0.
Eq.
232
follows from the event 4A-
Lemma B.10 (Adapted from Lemma C.3 in (1). Fix any R 2 0, [J] and [T]. Suppose
that the learning rate y satisfies S 4- (p 2(2R + 2 20
a.D In 6M and 0,g satisfies
10:g 0oll2 S for all E [i]- Furthermore, assume that R satisfies the following inequality:
317 2
12T
(In
6 2 M
(R <
T: + o 21n
(233)
56C (3)2
8
where:
(C 6M
12T
R R+ 2p
(2R 2P)
KB + 10++0/200 2
v3t +
(234)
Then, under the events Eg and Es.
12T
|haj+1 -Bell2 <
kB + og 21n
(235)
where haj [h(=1; Ozg)..... ..... h(x;; 0zy)]T e RR
Proof. We first assume that h - yell < TBB + a
12T 2
/3l holds. Here, by resorting the
3
same arguments as the proof of Lemma C.3 in 41, for any 0, 0' = Rd such that |0 -bol R, we have
(O)L 21),, - y vellalle(O', 0)]l
(236)
< L.00) - (()))
(237)
$ 2((V 0' (0) yellzlle(0', 0)1l2
6M (2R + 20 C) [c(4) In
(238)
+2
0 01 + 2 0) +lll0' 01
8
33

---

where e(0', 0) h,) - h, ()) T -0'- 0) with hz,0)= = (h(æ1; o)..... ,,,,; 0)) E R'
and G2( = (0; 0) E Rext From the upper bound of (,((') (,) by setting 0' R2 0' = VoVo. we have
0z;
1000~1VoL (0)
(239)
$ [o
(240)
+ 2 h1) -
0)112 + VoLL)))((--VLL((),,)) - - (V)
2 0. In SM 8 } E (0. 1). Furthermore, for any O' R", we {1 -
| 1
where
obtain the following inequality by combining the lower bound of L,(0') - (.) with the above inequality,
L, (V),(()) L,(
(241)
s 2cmp (,) y 1:00000-110000000000000001010001 0)1la]
(242)
(0) yellalle(O (V), 0)112 + 2||e - (0)
< 201p (0') - L.( + 1 (0) y.11 44|e0(0''')) 0)13
(243)
+ 2omp 1 (l)((0) v:112 + 201p
4
||e(e - VVLL 21 - (0)
< 2cmp (,(0") 7 (0) + Scmplle(0', 0)
(244)
le(00 - VV (0), 0)1 + 21ee(0- (0) + enp
where the second inequality follows from the Peter-Paul inequality, and the last inequality follows from (0) y: 1 < (0). Rearranging the above inequality with 0 = Org and O' Og. we have
10(0 - L,00
(245)
$ (1 - cnp) (1(5) - (o))) + conL)((0)
+8anplee(Oo- 012))1 2
(246)
le(0rst1,0
+ 2/ ((0gg(())) 0
cpp
2
12T
$ - c1-) (1.)) - Lo())) + tmp
TB + σ 2ln
t
(247)
2
Scnplle(Oo. 0,
le 0.j+i 01y)) + e 2g++1 0.5))
(
opp
Then, from Lemma B.15
le(O,, ot.)) = (00) - -G((0))) ((0 - -0rs))1
(248)
(h(z 0o) - (((1;(1g))) (x ...s), 0, 0cz))²
(249)
4t (R + C
6- 22+2
a.D
In
(250)
M
5
4t. (R + 2) 2(32
6 2D22
a.D
In
(251)
M
8
34

---

TB + a /2/2 12T
Furthermore, from | - yell2 -
v3t. we have
10:--1 0zyl = n7 Vor, (((0)))l22
(252)
1
|2Grss (hes yr) + 2(0 00)l12
(253)
4p
1
_
(I|Gr:)ll (Gtyilllbe - yellz + |10:g 00l12)
(254)
2p
v 2p
1
(2R + 122PPV 1/c/4) /CaaDDl In
6M
KB + 0/
21n
127
v3t + R
(255)
5
5
110041 - 0oll < R.
(256)
Combining the above inequality with Lemma B.13 have
R
R +
2)
C
(3)2 aDD
6 P M
[|e(Oug-1, 0.y))|
In
(257)
M
6
Therefore,
2
8cmplee(O0. 0c0)112
||e ( [ee(Ou+1: 0c.))12 + e/le (O::++1 0::+1100)))11
(258)
cpp
2
4tR
R + 2)
(33)2 a.D
6 6-2P+2M
8cnp +
+
In
(259)
cnp
M
3 4tR R 2
C3))
(3)2
6 2 PM
2
<
In
(260)
cmp
M
8
2
12T
S cnp
T-B + o 2
t,
(261)
where the second line follows from the fact that Scmp + 2 < 1/(ep)) holds due up 1/4 and e E (0. 1). Furthermone, the last line follows from the condition 233 with c 2 3/4. By combining
Eq. 225 with Eq. (261). have
[hast1 ye 12 1 =L((0rg+1) (0o)
(262)
(263)
12T
< (1 - ccp)[(( - L.(0)) + 2cmp
TB + vv
2
t
(264)
8
2
2cmp
kB + 2hn
12T
t
8
(265)
1- (1 cpp)
12T 8
=2 KB + v 2m
t.
(266)
By combining the event &s with the above inequality, we obtain the desired inequality.
Finally, check the assumption ||hes Vella < TB. + a 2 12T
31. If 0, ||
9:l12 < BB + 2 2n 12T /3t clearly holds from the event &n and h4o0 = O. Here, by applying
33t for j = Repeating the same arguments for j = 2, ... J. we obtain the inequality h!g yella S
the aforementioned arguments,
12T also verify ||h vill2 BB + a 2 /
12T' TB + o /222n 8 V3t.
35

---

Lemma B.11 (Adapted from Lemma B.2 in [11).
Suppose the following inequalities hold:
3r/² M p 56C(3)2 o,D
12T 6 2D M
(
BB +
o
2 In
(267)
5
((7)
a.D.I
kB KB+ 0V 2lm
12T
In
6 M
6MM In
S 1,
(268)
VM
6
8
1 4-1
p + 20)TTO
In 6M
(269)
0D
where:
R R= R+
(2R + 2P))
TC n
6M
BB + ov
2
12T
V3T +
(270)
2p
12T
T
2= kB + 0
2ln
(271)
8
p
Furthermore, we sel ((7)
D,D,T as
- 2/ 3/2
aDD
15)
2 C)C,, Ca.D
(272)
Then, under the events Eg, &g, and Es. the following inequalities hold for any t E [T] and j E [J]:
12T
T
10: - 00ll2 2
KB + 01
2
(273)
(7) a.D.T
12T
6. 2D+2
6M
0::5
01s
S
T: + oo 2
8 In 5
(274)
VM
5
Proof. We show by induction. Let us define Guj and hey as Guy = (g(1 (t.)...... g ( 0gg) )
Rpxt and haj [h(=1; Oeg)...........))......))...00 Max; Ou.)] E IR, respectively. First, Eqs. (273) and (74 clearly
hold if O. Next, fix any [J], and suppose that Eqs. (73) and (274) hold for any j < j. Then, as with Lemma B.2 in [41]. we have
0 0es l1,
< $1140- 20n (pIp + G,G,). (0us-1 0
+ 2m| (Gus-1- (Re: y:) 1|1
(275)
+ 2m G. |njji - G. (0n.-1 -
0o) 2
By resorting the similar argument of the proof of Lemma B.2 in 41 the first term is bounded from above as follows:
[4, 2n (eI, + G,G.)) (015-1- - 0.s 0 < (1 2np 00s-1 0
(276)
As for the second term of Eq. (275), from Lemma B.10 and Lemma B.15 we have
GGrj-1- G.) (hr:j11 81))
(277)
G Gell [1ags-11 - yr112
(278)
G Grll | 8ell2
(279)
12T
g( 0o)1
T:B + ov 2 5
(280)
< -3T
kB KB + 0 2
12T
(5) In g
6M
(281)
where:
36

---

Eq. 280
follows from Lemma B.10 the condition (267), and the induction hypothesis.
Eq. 281
follows from the event &3 and the induction hypothesis.
Furthermore, from Lemma B.13 and Lemma B.15
have
G. htjj-1 G. (0:--1 -00 112
(282)
G, hu. G. (0:- 0u)112
(283)
2I
C) 0.D
(3)
In
6.2 M
8
0
In SM
6
(284)
VM
By combining Eqs.
276 28
and 284 with Eq. (275). we have
01: O::
(285)
$ (1 2mp)|(0:35
0::j
011-1112
+ +2V3/TRM 1/2
12T TBB + -
TB
V C
a.
In
6M
(286)
2)
In 6.2
C.t a.D In 6M
VM
S 1/3
BB a 2
12T
(()
(5) a, In
6M
(287)
+ 4 M 1/2 R2 R + 2) + 2 20)) (3)
In
6. 22222
((4)
a. In
6M
0.D
8
8
127 1B 1B++ 1 21n 5
2V373/2 p-1/2/111/11 (9)) 6M
S 1-12
(288)
+16T p -2(R 2) 2 ())
a
in
6. 6.2D+2M
(9o In
6M
12T 0
T
$
KB 0 2n
(289)
p
where Eq.
289 follows from the condition (26
From the triangle inequality and Lemma B.9
Boll2 S 0..
8
+
0..s
(290)
2
12T
2
TB + 1
21n
(291)
5
Lemma B.12 (Adapted from Lemma C. in for any t E N4:
24
Under the event Es, the following inequality holds
VV 11 anD 11996
(6)
te S Ya
(292)
PVM M
where the constant (6) is defined in Lemma
B.6
37

---

Proof. Fix any 21. 21...., 2s X. Then,
1 In det (I, + p G.
(293)
Indet + p- K₁ + p-1 (G) -
(294)
- 2
det
(1+pp-KK Ki) + 2p
(4 p- Ki) -1 , G. K,)
(295)
1
S " +
(I, + K.) G G. -K:l1
(296)
2p
Vi
S it +
[INTK((2 Φ) (g(x,, 0u), g( 0o))
(297)
2p1
2..E ( .t...t)))
tv &V / a.D In In(96
$ 7/ +
(298)
PVM M
where:
Eq. (295) follows from the concavity of In det(-) and the fact that Vx In det X holds for any symmetric matrix X. In Eq. (295), (: represents the matrix inner product.
X
Eq.
296)
follows from the definition of 7--
Eq.
297
follows from
(Ie + p- K.)
1
I
F S V..
Eq.
298
follows from the event &g.
Lemma B.13. Let define (0) as GO (g(01; .). ,0,; 0)) E Bpxt Then, under the
event Ez, the following inequality holds for any R 2 0, E N+. and e E R such that |0 10-6ulle Gull2 S R:
[G < (2R+2P 2 2P / 1c In
6M 8
(299)
where the constants Ò and ((4) D are defined in Lemma B.4
Proof. From the definition of || 1I we have
(0) = Σ (g 0)1
(300)
< t0 a. (2R (2R 22 6M
(301)
8
Here, the last inequality follows from the condition Eg.
Lemma B.14. Under the event Ex, the following inequality holds for any N.:
|| + G.G. ( 8222 In 6M
(302)
where the constants Ò and a defined in Lemma B.4
38

---

Proof. Under the event &,, we have
pI, G,
|| p G
(303)
S Σ |1g( 00)g((;; 0
(304)
S p
Σ
(1 (0)g 0o) IF
(305)
=
Σ
g (a;;; 0n)
(306)
10 2D C In 6M
p
(307)
a.
where:
Eq. 304
follows from G.G. = Ei ( (a;; 0o) and the triangle inequality.
Eq. 306
follows from the fact that ||a::: || ||0:1 holds for any æ.
Eq. 307
follows from the event &g.
L
Lemma B.15. Under the event ε,, the following inequality holds for any S 1, R R20 0, and 0.6 0 Rp such that ||0 Boll2 R and ||@ Oull R:
2R (3) I1(x; 0) - Mx: θ) (g m: 0), 8)
0. (R + 2)
6 2P+2
In 5
(308)
M
where the constant (33) a is defined in Lemma 3.3
Proof. From Taylor's theorem, there exists [0, 1] such that
<(: 0) h(æ; 0) (g(:; 0), 0 0)
(309)
(0 0)
H
2; a0 + (1 (1- (1-a))) (0 -) 0) aθ + (1 - a)0) (0 0)
(310)
$ 0
0
H
(311)
2
M 0
0
2
H
x, ab + (1 - )]
(312)
2
Here, from the conditions of θ and 0, we have
0 0/
0
0p
+
0, - 0
S 2R
(313)
2
2
and
|o + (1 11------ 0u
< a
0 0
+ (1 a)
0 - - < R.
(314)
Therefore, from the event E,,
h(x: 0) - h(x; 0) - (g(x; 0), 0 0) $ 2
9 2
2. ab + (1 - a)]
(315)
2
2R
(3)
(3)
R + 2)
6. 2
D
ln
(316)
M
39

---

Proof of Theorem B.7 Suppose that the events E hold. As proposed in [30, we decompose the error term [f(x) h( 0.)l:
[(x) h(a:; 0:)
(317)
- ff(z) - ما((=)) + 1/((x)) (g(x; 0o). 0, - -Oo)l + [g( 0o), 0, - 0o) - h( 0,)l.
By combining the event Eg with Lemma B.12 the first term of Eq. (317) is bounded from above as follows:
lf(x) - [x((2))
(318)
V2B + σ
vp V
2
nt + In - (xx)(x)
(319)
'V 10 aD
(1996
) + In 8)
K
VēB+
2
m
0l-1(x))
(320)
vP1
PVM M
Furthermore, we obtain the following inequalities for the second term:
(x) (g(x; 0o), - -ooi
(321)
g( 0u) (pIp G.G.)) G.y. (g(a;; 0o), - -0o)
(322)
pー'
0. 0o (plp + G.G.)) G.yl |1 + G.G. (x)
(323)
111
2 +
+40
(2)
0, 00--0 00 - (pI, + G,G.)) -1 Giv.l
|| + G.G. (xxx))
(324)
0D
S -p1 V
K + +40
2
(c(7 D.D.T
kB + +aa oy
2n
12T
In
6 22
v ln
6.
VM
5
8
2
(1 212) 1/2
TB + ay
2ln
12T
T
(325)
V
5
0 + (T(4) a.
22
(2 In
6M
(x));
where:
Eq. (322)
follows from the feature space representation of j.. Actually, we have ji(
g (x; 0o) (p + G. G.)- y, = g(x: 0,) T (pI, + G.G.) Giy,, where the last
equality follows from the matrix identity Ge(pI, + G. G.) (pIp + G,G,)) G (e.g., Lemma 3 in 29
Eq.
323
follows from the fact that (21, 22)
<
(z A-1)) (z.] Az₂) <
(z] A 2 ||||||/ holds for any positive definite matrix A E RPxP and 21, 22 RP.
Eq. (324 follows from (x(x)) S vk(2, s vie + (2) where the last inequality
follows from the event Eg.
Eq.
325 follows from Lemma B.9 and Lemma B.11
40

---

By using Taylor's theorem for the third term, there exist a E [0, 1] such that:
[x;; 0,) (g(0; 0o), O. On)l
(326)
2 [0: 0o) (aB: + (1 - a) Bu)
(327)
v 2 0. 0olla Ha0; + (1 a))))( 00)
(328)
1
$ 0: 00ll
H (a0: + - a)oo
(329)
C2
p2 TB
aDD
2l
127
In
6 6-29 2
(330)
8
where Eq. 327
follows from h(x: 0o) = 0 holds for any x E X, and Eq. (330 follows from
Lemma B. and the event & Finally, since the events & holds with probability least 1
from Lemma B.8
we obtain the desired result by aggregating Eqs. (320). 325 and (330
C Proof of Theorem
Theorem C.1 (Detailed version of Theorem 3.3
Suppose that Assumption 3.1 holds. Fix any Furthermore, suppose that the number of en- Then, if the learning rate nj satisfy
5 E (0. 1), a 2 1, > O, and DD 2 2.
semble M sufficiently large satisfy Eqs. 162 (65).
S 4- (o+ 1 2(2 + 2 TC a In GM
with probability at least - ô, the following in-
8
equality holds:
1447 (((3
0.D
12T
6 6-2
RT S
kB +
In
In
(331)
VMp
8T
T
[C (6)
aD
212
+ B
+r+
(332)
In(1 + p-22
PVM
Furthermore, if M and J is sufficiently large to satisfy the following additional three conditions:
where 3 is defined in Theorem B.1.
144T (3) D.D
12T
6
2D42
TB + a
2
In
1
(333)
VMp
5
T (C 0D
12996
1
(334)
PVM
V 1e + (0
(T)
A.D.T'
TB + vV
2m
12T
In
6 2
In
6M
VM
8
8
8
(335)
(1 112
TB /
2ln
12T
8
1 p
p
-
(C(4) (4)
20
22D
6.M
then,
1 ( 2)
8T(7T 1)
Rr 11 22B 1+
vp
2
In(1 + + 2)
(336)
The proof Theorem C.I leverages the following lemma, which describe the relation between the sum of 5 (xx) and MIG.
41

---

Lemma C.1 (Lemma 5.3 and Lemma 5,4 in (32). Fix any T E N+. Then, for any sequence
Siy.. To the following inequality holds:
FT
cz (xx) S
(337)
+ p-
Proof of Theorem
C.1
From Theorem B.1
with probability at least 1 - 6,
RT Σ [f(a)) - s(x:))
(338)
(4 aD
12T
6.
2D+M
BB 0 2222
2
In
2/
Σ
81-1(
(339)
VMp
8
8
1=1
1447 a.D
127
6 2
8T
kB + 0V 2 In
In
3
(340)
VMp
8
8
In p-
c() 0,D
12T
6. 22+2
TB o 2
In
VMp
(341)
T (C 0DD
(n(96)221244
8T
+
"T +
In(1 p-2)
PVM
where Eq.
339
follows from the definition of æ, and Eq. 330 follows from Lemma C.1
Further-
more, Eq.
341 follows from Lemma B.12
D Proof of Lemma 4.1
Proof. Fix any function f HTNTK- According to Mercer's representation theorem (see, e.g.. Theorem 4.5.1 in (33), there exists sequence (Wn.)) such that En= Na.a
E Wn. < co and
Na Wn. (//22nns()))
f(-)
(342)
Furthermore, the RKHS norm [[]]|NN is obtained as ||
E
Na. w Ej=1
Note that, similar to the TNTK, the ReL.U-based NTK can be expanded using spherical harmonics (Yng) as follows (see, e.g., 35
Nam
KNTK σ)
(343)
n=
where (Ān)nEN are the eigenvalues of the NTK. Here, the function f can be written as
Na.
(V
An Xm
f()
Wai
X
(2)2)n)()).
(344)
==
By noting both TNTK and NTK can be expanded by (Yn,),, the following equation holds from Mercer's representation theorem:
Nam
An
If
W
(345)
X
n=0
42

---

According to Bietti and Bach (6, An θ(n and there exists a constant Ca. > 0 such that Ca S An- Combining this with Lemma 3.1 have:
Nan
(1) wn C C exp (- (1 1+ 402
1 Dri)
I S
(346)
j=1
Since n² exp (- In (1+ Inz) Dn) (as 00), there exists a constant Co,d such that nd exp (- (1 + ia= Dn) S Ca, holds for any N. Thus,
Nd.
II S C. TT C.L Ca.d
C. caall.llen <0.
(347)
n=0 f=1
From the above, it follows that HTNTK HNTK.
E Helper Lemmas
Definition E.1 (Sub-Gaussian norm, Definition 2.5.6 in 33 Let X be a real-valued random variable. Then, the following quantity ||X]] 2l is called the sub-Gaussian norm of X:
X2
X 11 = inf t 2
0
E
exp
2
(348)
t2
Moreover, 1| < 30 holds, we call the random variable sub- Gaussian random variable. Definition E.2 (Sub-exponentic norm, Definition 2.7.5 in (39).. Let X be real-valued random variable. Then, the following quantity [1 is called the sub-exponential norm of X:
| = inf { 0
X
}
E
exp
(349)
Moreover, X
1| < oo 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 .NN x be indepen- dent, mean-zero, sub-Gaussian random variables. Then, for every 2 the following holds:
et2
IP
Σ
X
2t
S
2exp
(350)
|
1=
where e is an absolute constant.
Lemma F.2 (Bernstain's 's inequality, Theorem 2.8.1 in (39). Let NI...., XN be independent, mean- zero, sub-exponential random variables. Then, for every 2 0, the following holds:
IP
Σ
X;
21
<
exp
-e
t
t
(351)
|| Lizi
max
X
where e is an absolute constant.
Lemma E.3 (Centering, Lemma 2.6.8 and Exercise 2.7.10 in (3)) For any sub- Sabh-Gassian random variable X, X| E[ I C holds. Furthermore, for any sub-exponential random variable Y, | [|]]]| I <CIlYli llv holds, where C' > 0 is an absolute constant.
Lemma E.4 (Product sub-Gaussians is sub-exponential, Lemma 2.7.7 (39]). Let and Y be sub-Gaussian random variables. Then, XY is sub-exponential random variable whose sub- exponential norm satisfies
|X|l,, Σ |X
Details of numerical experiments
F.1 Our implementation of algorithms
Here, we provide additional information on the implementation the ST-UCB and NN-UCB algorithms. Our implementation includes the following three simplifications:
43

---

(a) In the calculation of the gradient in line of Algorithm we use g(æ; 01-1) from the previous round, rather than the initial gradient g( 80)
(b) In the regularization of parameters in line of Algorithm do consider the residual from the initial parameters On. In other words, we apply L.2 regularization directly to the parameters themselves.
(c) Instead of initializing 0g described in Sec. 3.1 initialized On by the Glorot's uniform initializer [17).
It should be noted that the simplification (a) is the same implementation the original NN-UCB, while the other simplifications are for the sake of simplicity in implementation. We train two models (ST, NN) using stochastic gradient descent (SGD) with 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 performed in all rounds, with mini-batch size of 64 and 5 epochs, and we do not use early stopping.
F.2 Parameter sensitivity
In the results shown in Fig. of the experimental section, we presented the outcomes with optimal hyperparameters of 3. Here, the experimental results for each parameter e E (0.05, 0.2). 8 E (0.01, 0.1,1} are summarized in Fig. (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 e-greedy based policies when 3 = 0.01. In the f(!) 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
G Summary of the existing works
G.1 Derivation of TNTK
Our analysis relies on the TNTK derived by Kanoh and Sugiyama 21 soft tree ensemble model, we have
From the definition of the
M oo h(:;; ((m)), V hoim)
(Voh(a; 0), Voh(a;00)
(352)
M
If 0 (O, Ip). ((V gim: h(2;; (1:;01 (m))) Vi Max; ((m)))))m((M) is mutually independent; there- fore, from the law of large number, the inner product (Voh(x; 0), Veh(æ; 0)) converges to
EKVV Tax:; ((m)), V Vernyhie h(x; [(m)))] in probability as M - co. Kanoh and Sugiyama [2] shows that B[(V (erm @ems h(:; ((m)). V Veom)h(z; h(2; ((m) equals the expression in Eq. (I) by relying on the recursive expressions of the soft tree (such as Eq. (8T).
G.2 MIG and effective dimension
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
d = Tr (TT(K(K + pIr)
(353)
Due to the following inequality 99 the MIG is bounded from above by the worst-case effective dimension up to logarithmic scale:
In det(p Kr + Ir) s Tr (2 (Kr + pIr) In(p Kr + 1)).
(354)
44

---

Mlrgmedy
nlogwedy
21:13
30
100
350
250
380
30
160
350
200
25
330
30
160
350
26
330
K
0.01,
0.1,
12
1842 Micresd
184333
K 40, = 0.01, 0.05
40, 5 0.1, = 0.1
K 40,
1,
0.2
MHOO
N6400
Miggedd
Wicredy
90
000
350
100
350
100
350
185
R
0.01,
60, 0.1,c
60,
1,c
Figure The average cumulative regret with one standard error in the real-world dataset.
1E: muCC Tigredy
MEL STACC 7egreed
18403
00
S7.31ed
30
100
310
30
100
310
90
180
300
= 0.01,
0.05
0
0.1,
c 0.1
1, 6 0.2
230
Mkipeedy
Miggeedy
Alogwedy
92
100
393
100
190
110
190
(2)
0.01,
(2)
stucc
STaresyy
Stares
10408
(3) /8
0.01, 0.05
[1)
0.1,
0.1
(8)
0.2
Figure 4: The average cumulative regret with one standard error in the synthetic dataset.
45

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
The details of our contributions summarized in the abstract and introduction
are given in Sec. 3.2 and Sec. The sections in which the details of each contribution
described are explicitly stated in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The assumptions for our main result are given Assumption 3. and the discussions of their validities are described in Remark 3.1.
Guidelines:
The answer NA means that the paper has 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 separate "I "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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
46

---

Answer: [Yes]
Justification: The assumptions for our main result is given in Assumption 3.1 The complete
proofs of our main results are given in Appendix A B
and D
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The detailed information for our experiment is given in Sec. and Ap- pendix F.I
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
47

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification: We are not yet ready to release the required codes and will do so as soon 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. and Appendix F.1 is sufficient to reproduce numerical experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
sublic/guides
CoodeSubmissionooll11 httpe//ggiiieee//oeubbbiiiiee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
cilips.cc/publle httee//lliccgguuddeeeeeeeeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The information of our model hyperparameter given in Sec. 5 and Ap- pendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The error bars, which represent one standard errors, are given in our experi- mental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
48

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Since our experiments are limited to simple problem setups and our contribu- tions are primarily theoretical, the computational resources used not significant.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http::///oorrrpp.coo..tttttttitt
Answer: [Yes]
Justification: We confirmed that our paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration 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.
49

---

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), faimess 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 tied to particular applications, let alone deployments. However, if there is 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 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 challenging, and many papers do not require this, but encourage authors to take this into account and make 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 UCI-Maching Learning Repository in Sec.
Guidelines:
The answer NA means that the paper does not 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 used and, 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.
50

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 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 the supplemental material is fine, but if the main contribu- tion 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.
15. 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
51

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
52


Reviews:
[{"review_id": "HvW7rmItIC", "reviewer": "Reviewer_ghBb", "summary": "The paper investigates soft tree ensemble model for reward modeling in bandit algorithms.", "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": "The paper did discuss the theoretical limitation.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The work provides comprehensive formal evidence for the proposed methods. \nThe empirical study is also comprehensive.", "weaknesses": "Not sure if there is some new insights beyond other similar works that utilized the NTK theory such as Neural Thompson Sampling.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments.\n\n> 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?\n\nFrom a practical perspective, the performance of a bandit algorithm depends on how accurately the reward model can represent the underlying data structure.\nTherefore, our soft tree-based algorithm is expected to perform better than the ReLU-based algorithm on tabular data, where existing soft-tree regression works have reported high empirical performance (e.g., [1,2]).\n\n- [1]Popov, Sergei, Stanislav Morozov, and Artem Babenko. \"Neural oblivious decision ensembles for deep learning on tabular data.\" arXiv preprint arXiv:1909.06312 (2019).\n\n- [2]Hazimeh, Hussein, et al. \"The tree ensemble layer: Differentiability meets conditional computation.\" International Conference on Machine Learning. PMLR, 2020.\n\nFrom a theoretical perspective, our analysis shows that the soft tree-based ST-UCB algorithm has superior performance compared to the ReLU-based NN-UCB algorithm,\nalbeit at the cost of a smaller hypothesis space for the soft tree model (see Section 4).\nWe believe that this result will motivate practitioners to use our soft tree-based algorithm instead of the ReLU-based algorithm,\nas the superior performance of ST-UCB is guaranteed if the underlying reward function lies within the hypothesis space of the soft tree model.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "gyAiVITdLx", "reviewer": "Reviewer_PrZ2", "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.", "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?\n- The exponential eigenvalue decay is surprising. Could you please provide some intuition on how the improvement can be achieved as compared to NTK?\n- What is the key difference between NN-UCB and ST-UCT in their mechanism?", "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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "This paper provides solid theories for Tree Neutral Tangent Kernel (TNTK) and the suggested algorithm. The contribution of these theories seems significant. Also, the experiments demonstrate that the algorithm the ST-UCB algorithm performs well.", "weaknesses": "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:\n\n- The first paragraph in the first section is unclear. How various combinations of users and items can be connected to unobserved actions?\n- 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.\n- Citation formats should be corrected.\n- For Section 2, lines 107-120 should be clearer. Especially, lines 111-113 seem to have some errors.\n- The proofs in Appendices need much work for improved presentations.\n- The statement of Lemma 4.1 seems wrong.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their useful feedback and suggestions.\nTo address the readability issues that the reviewer kindly pointed out, we will carefully revise our paper as follows:\n\n- The description of TNTK:\n    - In Section 2, we will add the detailed introduction of TNTK, including its definition.\n    - Furthermore, in the Appendix, we will add an independent section that describes the detailed derivation of TNTK.\n- The proofs in Appendices:\n    - We will delete redundant expressions as much as possible to make the proofs more concise and coherent.\n    - Furthermore, we will add brief proof sketches in Appendices A, B.1, and B.2.\n- The description about effective dimension and MIG:\n    - In Section 3, we will add a description of the effective dimension by relating it to MIG.\n    - Furthermore, in Appendix, we will add an independent section that summarizes the effective dimension and MIG.\n\nWith these modifications, we believe that the reviewer's concerns can be resolved.\n\nBelow, we provide answers to the reviewer's questions.\n\n> 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?\n\nOur analysis **does not** assume the independence of noise sequence $(\\epsilon_t)$; therefore, our conditional sub-Gaussian assumption is milder than the sub-Gaussian noise assumption with independence. \nPlease note that the conditional sub-Gaussian assumption is already utilized in existing works on linear or kernelized bandits (e.g., see [1, 2, 3]).\n\n- [1]Abbasi-Yadkori, Yasin, Dávid Pál, and Csaba Szepesvári. \"Improved algorithms for linear stochastic bandits.\" Advances in neural information processing systems 24 (2011).\n- [2]Abbasi-Yadkori, Yasin. \"Online learning for linearly parametrized control problems.\" (2013).\n- [3]Chowdhury, Sayak Ray, and Aditya Gopalan. \"On kernelized multi-armed bandits.\" International Conference on Machine Learning. PMLR, 2017.\n\nIn addition, these existing works also do not assume the independence of the noise sequence.\n\n\n\n> The exponential eigenvalue decay is surprising. Could you please provide some intuition on how the improvement can be achieved as compared to NTK?\n\nThe difference in the eigenvalue decay behavior between NTK and TNTK mainly arises from the difference in smoothness between NTK and TNTK.\nSpecifically, TNTK is infinitely differentiable over $\\mathbb{S}^{d-1} \\times \\mathbb{S}^{d-1}$, whereas NTK is not (see, e.g., [4]).\nOur analysis shows that TNTK achieves exponential eigendecay by carefully leveraging existing result on the dot product kernel (Definition A.1 and Lemma A.1), \nwhich fundamentally relies on the infinite differentiability of the underlying kernel.\n\n- [4] Bietti, Alberto, and Francis Bach. \"Deep Equals Shallow for ReLU Networks in Kernel Regimes.\" ICLR 2021-International Conference on Learning Representations. 2021.\n\n\n> What is the key difference between NN-UCB and ST-UCB in their mechanism?\n\nThe main difference between NN-UCB and ST-UCB lies in the rate at which the width of the confidence bound converges to zero.\nSpecifically, in ST-UCB, the width of the confidence bound given by Theorem 3.2 converges to zero at a rate of $\\tilde{O}(1/\\sqrt{T})$.\nIn contrast, the width of the confidence bound used in NN-UCB generally does not converge to zero unless additional assumptions on $\\mathcal{X}_t$ are introduced (Section 4, Lines 253-255).\nThis difference in the behavior of the confidence bounds results in the different rates of cumulative regret for ST-UCB and NN-UCB, as discussed in Section 4.\n\n\nFurthermore, we would like to address the comments provided by the reviewer as follows:\n\n> The first paragraph in the first section is unclear. How various combinations of users and items can be connected to unobserved actions?\n\nWe will revise this paragraph in revision to improve clarity. The content we intended to convey in this paragraph is as follows:\n\nIn situations where the size of the action (arm) candidate set $\\mathcal{X}$ can be extremely large compared $T$ to the total number of steps (i.e., $|\\mathcal{X}| \\gg T$), \nit is difficult to apply conventional finite-armed bandit algorithms that assume the independence of arm rewards.\nSpecifically, when assuming the independence of arm rewards,\nit is necessary to observe each arm at least once to estimate its reward; however, it is infeasible to run when $\\mathcal{X}$ is enormous.\nTherefore, in such scenarios, it is essential to estimate the rewards of all actions (arms) in, \nincluding unobserved ones, from limited observational data and to balance the trade-off between exploration and exploitation. \nAs an example of such situation, this paper considers a recommendation system where the action candidate set $\\mathcal{X}$ is given by the combination of users and items.\nAs mentioned in [5], in large-scale recommendation systems with a large number of user or item candidates, the action candidate set $\\mathcal{X}$ can become extremely large.\n\n\nLastly, it should be noted that examples of large-scale arm candidate sets are not limited to recommendation systems.\nMany such examples of applications have been reported in existing works (e.g., [6], [7]), and large $\\mathcal{X}$ setting is a common motivation for introducing model-based bandit algorithm like kernel bandits (see, e.g., Introduction in [6]).\n\n- [5]Vanchinathan, Hastagiri P., et al. \"Explore-exploit in top-n recommender systems via gaussian processes.\" Proceedings of the 8th ACM Conference on Recommender systems. 2014.\n- [6]Chowdhury, Sayak Ray, and Aditya Gopalan. \"On kernelized multi-armed bandits.\" International Conference on Machine Learning. PMLR, 2017.\n- [7]Kassraie, Parnian, Andreas Krause, and Ilija Bogunovic. \"Graph neural network bandits.\" Advances in Neural Information Processing Systems 35 (2022): 34519-34531.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "RhNWMXNix7", "reviewer": "Reviewer_SWN3", "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.", "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": "The paper clearly indicates that the imrpovement they make over exisiting work comes at the cost of a reduced hypothesis space.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper proposes a new approach, to the best of my knowledge.\n\nIt is shown that their model is an extension to the existing neural bandit case using.\n\nIt improves it regret bound to be sublinear  a clear improvement over neural bandits.\n\nA new confidence bound on for their model is provided.", "weaknesses": "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.\n\nMinor 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the overall positive assessment of our paper.\nWe describe the answers to the question of the reviewer\n\n> Is there a point where M is to large and the tree ensemble becomes too complex?\n\nIn theoretical perceptive, the huge $M$ improves the regret even if the complexity of the soft tree models becomes overly large.\nThe theoretical superiority observed in such overly complex models is similar to the recent theoretical findings on NTK in regression problems (e.g., [1], [2]).\nOn the other hands, in practical perceptive, our regret analysis (Theorem 3.3) need the learner to choose sufficiently small (large) learning rate (step size) of the gradient descent;\nSuch theoretical demand makes it difficult to apply ST-UCB algorithm for overly large soft tree models in practice, and we leave additional effort to more computationally efficient algorithm as future work.\nFinally, we would like to note that such high computational demands also exist in current neural bandit algorithms (e.g., NN-UCB [3]). Therefore, we believe that the high computational requirements described above do not diminish the significance of our contributions.\n\n- [1] Jacot, Arthur, Franck Gabriel, and Clément Hongler. \"Neural tangent kernel: Convergence and generalization in neural networks.\" Advances in neural information processing systems 31 (2018).\n- [2] Arora, Sanjeev, et al. \"On exact computation with an infinitely wide neural net.\" Advances in neural information processing systems 32 (2019).\n- [3] Zhou, Dongruo, Lihong Li, and Quanquan Gu. \"Neural contextual bandits with ucb-based exploration.\" International Conference on Machine Learning. PMLR, 2020.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "fhArt52Qe7", "reviewer": "Reviewer_X7L7", "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.", "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": "Authors have discussed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The research applies neural bandit (NB) theory to non-neural network models, which extends the applicability of stochastic bandit algorithms and also provides new regret minimization algorithms for tree-based models.\n2. The paper not only has a proof of theory and an in-depth analysis of the properties of the soft tree ensemble model, but also conducts some experiments to verify the performance of the algorithm.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. \n\n> 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.\n\n> 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.\n\nWe will make an effort to consider a wider range of applicability in future work.\nHowever, since the theoretical assumptions (Assumption 3.1) of our analysis rely only on the standard set of assumptions in the existing neural bandits literature (as described in Remark 1), \nthe applicability of our theory is at the same level as that of existing neural bandit algorithms (e.g., NN-UCB [1]).\nTherefore, we believe that the applicability of our algorithm does not diminish the significance of our contributions.\n\n- [1] Zhou, Dongruo, Lihong Li, and Quanquan Gu. \"Neural contextual bandits with ucb-based exploration.\" International Conference on Machine Learning. PMLR, 2020.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)