Bi-level Hierarchical Neural Contextual Bandits for Online Recommendation
Authors: Yunzhe Qi
Yao Zhou
Yikun Ban
Allan Stewart
Chuanwei Ruan
Jiachuan He
Shishir Kumar Prasad
Haixun Wang
Jingrui He
Venue: Accepted by TMLR ()

Abstract: Contextual bandit algorithms aim to identify the optimal choice among a set of candidate arms, based on their contextual information. Among others, neural contextual bandit algorithms have demonstrated generally superior performance compared to conventional linear and kernel-based methods. Nevertheless, neural methods can be inherently unsuitable for handling a large number of candidate arms due to their high computational cost when performing principled exploration. Motivated by the widespread availability of arm category information (e.g., movie genres, retailer types), we formulate contextual bandits as a bi-level online recommendation problem, and propose a novel neural bandit framework, named $\text{H}_{2}\text{N-Bandit}$, which utilizes a bi-level hierarchical neural architecture to mitigate the substantial computational cost found in conventional neural bandit methods. To demonstrate its theoretical effectiveness, we provide regret analysis under general over-parameterization settings, along with a guarantee for category-level recommendation. To illustrate its effectiveness and efficiency, we conduct extensive experiments on multiple real-world data sets, highlighting that $\text{H}_{2}\text{N-Bandit}$ can significantly reduce the computational cost over existing strong non-linear baselines, while achieving better or comparable performance under online recommendation settings.

Published in Transactions on Machine Learning Research (01/2026)
Bi-level Hierarchical Neural Contextual Bandits for Online Recommendation
Yunzhe Qi', Yao Zhou?, Yikun Ban', Allan Stewart', Chuanwei Ruan Jiachuan He², Shishir Kumar Prasad Haixun Wang", Jingrui He
University of Illinois Urbana- Champaign, Google, Instacart, EvennU
(yunzheq2, jingrui @illinois.cd yuozhooccosmss@@ggggecccoo
Work done while working at Instacart.
Reviewed on OpenRevicw:
Abstract
uantextual bandit algorithms aim to identify the optimal choice among a set of candidate arms, based on their contextual information. Among others, neural contextual bandit algorithms have demonstrated generally superior performance compared to conventional linear and kernel- based methods. Nevertheless, neural methods can be inherently unsuitable for handling a large number of candidate arms due their high computational cost when performing principled exploration. Motivated by the widespread availability of arm category information (e.g., movie genres, retailer types), we formulate contextual bandits as bi-level online recommendation problem, and propose a novel neural bandit framework, named H2N- Bandit, which utilizes bi-level hierarchical neural architecture to mitigate the substantial computational cost. found in conventional neural bandit methods. To demonstrate its theoretical effectiveness, we provide regret analysis under general pver-paramcterizatiin scttings, along with a guarantee for category-level recommendation. To illustrate its effectiveness and efficiency, conduct extensive experiments multiple real-world data sets, highlighting that HęN-Bandit can siguificantly reduce the computational cost over existing strong non-linear baselines, while achieving better or comparable performance under online recommendation settings.
1 Introduction
Contextual bandits are a type of multi-armed bandit (MAB) that leverages contextual information to navigate the exploration-exploitation dilemma (Auer et al., 2002), in online scttings without state transitions or sequential dependencies. Unlike greedy algorithms that only exploit known information (He et al. 2017), contextual bandits can utilize principled exploration strategies to achieve improved long-term outcomes, making them valuable in various real-world applications, such as medical experiment (Durand et al. 2018
and personalized recommendation (Li et al. 2010 Wu et al. 2016). For example, consider online grocery platform that decides which retailer to recommend. It can either exploit its knowledge of user's preferred retailer or explore new one to discover a potentially new match. Principled exploration strategies, such as Upper Confidence Bound (UCB) (Li et al.) 2010), enables the platform to balance this trade-off, by adaptively exploring new options based on their levels of uncertainty. By intelligent exploration, the system can effectively uncover user preferences and improve long-term satisfaction (Li al. 2010 2011).
Among various types of contextual bandit algorithms, neural contextual bandits (Zhon et al. 2020 Zhang
et al. 2021) have recently risen to prominence, due to the superior representation and learning capabilities of neural networks. However, nontrivial challenge arises from their computational cost, particularly when dealing with a large pool of candidate arms (e.g., a large number of candidate retailers). One major reason is that neural bandit methods with principled exploration typically require gradient computation for each arm to support effective exploration, making them less viable real-world applications (Jia al. 2022). To address this challenge, we leverage widely available arm hierarchical information (e.g., retailer types, movie genres) (Hu) et al. 2013 Zhu et al. 2021) for refined recommendation strategy. Our approach differs from conventional

---

Published in Transactions on Machine Learning Research (01/2026)
contextual bandit algorithms that operate in 'flat' action space (Li et al. 2010: Valko et al. 2013 Zhou
et al.
2020), by utilizing the arm category hierarchy to efficiently narrow down the candidate pool before the final arm selection. Inspired by the potential of arm hierarchies to improve bandit performance and efficiency Hong ct al. 2022 Zuo et al., 2022 Aouali ct al. 2023), our work pioncers the hicrarchical neural bandit rramework. This formulation is uniquely capable of achieving strong recommendation oulcomes in potentially complex settings with unknown, arbitrary arm reward mappings (Zhou et al., 2020). Specifically, we formulate a bi-level hierarchical strategy to improve efficiency: first, the category-level model selects small subset. of high-potential arm categories. Second, with an arm-level model, the arm recommendation is performed by only selecting from the candidates within this pre-filtered set. This approach can substantially reduce computational cost, as the final selection is performed on a dramatically smaller pool of candidates, rather than the entire candidate arm space. Distinct from conventional greedy recommendation methods that utilize the item category information (Cai et al. 2021; He et al. 2016), we tackle the inherent innoiitation-eploraatio dilemma with bandit-basod principled exploration.
Meanwhile, this bi-level hierarchical strategy can also adeptly navigate the exploitation-explorabie dilemma at the category level, facilitating more efficient exploration by preventing unnecessary effort on unpromising categorics. For example, consider a user with an unknown scafood allergy. Instead of lcarning this aversion for individual arms (e.g., learning from arm contexts with category information), our hierarchical design can aggregate feedback at a higher level. From negative interactions, the category-level model can perceive that the entire "seafood" category is umpromising, allowing the system to prune seafood-related arms before the computationally expensive arm-level scoring phase, yielding dual benefit: significant computational savings and more sample-efficient exploration, as the model learns to avoid unpromising options more efficiently.
Motivated by real-world application scenarios and to tackle the aforementioned challenges, we propose a novel contextual bandit framework named Bi-level Hierarchical Neural Bandit (H₂N-Bandit), which leverages the arm category information to formulate a highly efficient yet effective recommendation strategy. To manage the potentially vast number of candidate arms, HyN-Bandit formulates contextual bandits into a bi-level hierarchical recommendation problem, where it initially reduces the size of the candidate pool by filtering arm categories, thus streamlining the selection process for the final arm recommendation. Our H-ndBa not only reduces the computational demands by utilizing filtered pool of candidate arms, but also incorporates two types of principled exploration strategies for category-leve and arm-level recommendations. This bi-level design improves efficiency while effectively addressing the exploitation-exploration dilemma across both levels. Our main contributions can be summarized as follows:
Problem Formulation and Proposed Framework: We formulate and study the problem of hierarchical neural contextual bandits, where a learner is expected to navigate a bi-level exploitation-explratii trade-off across both arm categories and individual arms under unknown, potentially complex reward mappings. Unlike existing hierarchical works that rely on assumed reward priors, HęN-Bandit is the first stochastic neural bandit framework capable of handling arbitrary arm reward functions. By leveraging the arm-category hierarchy, HşN-Bandit can perform principled exploration effectively and efficiently at both levels. This structural design allows it to prune the candidate pool, focusing on promising arms and improving computational efficiency, while maintaining strong recommendation performance.
Under general over over-paramete paraamttttctiiiioonn settings for neural bandit, we establish the first regret analysis for hierarchical stochastic neural bandit. To handle the absence of true category rewards, we develop comprehensive theoretical framework that jointly optimizes both category and arm-level models. Our framework achieves greater generality by avoiding the restrictive arm separateness and reward-prior assumptions, which are common in existing works. We also provide a theoretical guarantee for category-level recommendation of H-N-Bandit, demonstrating the effectiveness of our bi-level design and instantiation.
Thcorctical Analysis:
Experiments:
Extensive experiments are performed on public real-world data sets, where we demonstrate that our approach not only delivers better or comparable performance compared to strong existing stochastic bandit baselines, but also offers a substantial advantage in computational efficiency. We further investigate our framework's properties and capabilities through additional experiments, including a parameter study, an analysis of the category-level strategy, and extension of HgN-BBnndi to three-level hierarchy settings.
2

---

Published in Transactions on Machine Learning Research (01/2026)
2
Related Works
With assumed linear reward mapping functions, lincar contextual bandit algorithms (Chu ct al. 2011 Li et al. 2010: Auer et al. 2002 Abbasi- Yadkori et al.)
2011 are first proposed to tackle the exploitation-explraateee
2011 Li et al. 2010) utilizes linear regression, with the UCB for principled exploration. Afterward, to formulate the reward and confidence bound estimation for non-linear settings, kernelized bandits (Valko et al.
dilemma. In particular, Lin-UCB (Chu et al.
Krause & Ong 2011 Deshmukh et al. 2017) assume the reward mapping functioon belongs to the Reproducing Kernel Hilbert. Space (RKHS). Meanwhil hile, collaborative
2013:
algorithms (Gentile et al. 2014 Li ct al.)
2019
Ban & He 2021b; Gentile et al.) 2017 Cesa-Bianchi et al.
2013 Wu et al. [016 [Ban et al. 2024 SS et al.
2025) try to incorporate similar users based on the estimated
or known user correlations perform user-item collaborative filtering (Li et al.
2016 Several works leverage
arm hierarchy information (Hong et al.) 2022 Zuo et al. 2022 Aouali et al.]
2023 Yang et al. 2020a, Sen
et al.
2021 but rely on pre-defined reward mapping priors tailored to specific settings. Yang et al. [2020a]
addresses resource-constrainee linear bandits with budgeted recommendations, Hong et al. (2022) assumes a
tree-structured action space with known priors and fixed cardinality under Bayes regret, and Sen et al. (2021
studics top-k bandits with realizability assumptions (c.g., known function class). These scttings differ from our stochastic neural bandit, as the pre-defined reward assumptions can fail in real-world applications.
Neural bandit algorithms leverage the representation power of neural networks, to relax structural assumptions on reward mappings. Inspired by Neural Tangent Kernel (NTK) (Jacot et al.) 2018), prior works apply fully-connected (FC) neural networks for reward estimation, with NTK-based UCB (Zhou et al.
2020:
Ban
let al., 2021 Ban & He 2021a: Qi et al.; 2022 Kassraie & Krause 2022 Gu et all 2024 Dai et al.
2023
Ban et al. 2024) or Thompson Sampling (Zhang et al.) 2021) for exploration. Meanwhile, Ban et al. (002))
Qi al. (2023) utilizes the second neural network to learn the confidence ellipsoid for adaptive exploration.
However, these approaches require searching across the entire candidate arm pool, which introduces additional
computational challenges, especially when the number of candidate arms is large in practice. While Osband
et al. (2023); Zhu & Van Roy] [2023a b) employ heuristic EpiNet-style uncertainly estimation for improved efficiency, they typically assume fixed, known action space and lack theoretical guarantees. This limits their applicability in our stochastic neural bandit settings, where rigorous regret analysis is a critical requirement,
and the arm space is typically unknown, dynamic, or unbounded (Zhou et al. 2020 Zhang et al. 2021
3 Problem Definition
Given a finite horizon T E N,, consider a fixed pool C of arm categories, and each calegory E C is associated with unknown category context distribution. As arm contexts can include the background from both item and user perspectives, a sctup common in applications such as 'Online Personalized News Recommendation (Li et al. 2010), it is natural to reason that arm contexts can capture information from both sides.
In each round t e [T], we will receive a subset of arm categories C, C. For instance, retailer categories available can vary across regions (c.g., large wholesale chains are typically absent in rural arcas). For cach category c E C,, the collection of Ka,, candidate arms is denoted by Xx,, = e..,...... FF, (Ka..)), drawn from the category-specific context distribution, with |Ka,1l = Ke,- Conscquently, the overall set of candidate arms, irrespective of their categories, is given by X; = U.,c, Xa,s, with total size |X|| = K. We generally have [z]] = K > [C.]. Thus, there are K candidate arms for selection in round in total, following the stochastic contextual bandit setting (Zhou et al.) 2020). By definitions, an arm can belong to multiple categories: for some c, E Ce, it is possible that Xe, n Xx + 0. For example, a 'Vegan Mexican" restaurant belongs to both the "Vegan' and 'Mexican' categorics. With d-dimensional arm context 20 E X2, i E [Ke,l. we consider (6) its reward ret is given by
( re. - h
(8) E.1
where ha(-) represents the unknown arm-level reward mapping function, and e is zero-mean a-sub-Gaussian noise, consistent with prior studies (Zhou et al. 2020 Zhang et al., 2021). Considering practical scenarios like online rocommendation with normalized ratings, for an arbitrary arm æ and its reward r, we consider the bounded expected reward E.[r] = hz()) E [o, 1), similar to Gentile al. 2014 2017); Ban & He (2021b); Qi
et al. 2023 In round i, the learner aims to choose one arm a, X. with the macimal expected reward.
3

---

Published in Transactions on Machine Learning Research (01/2026)
Learning Objective. Within the framework of stochastic contextual bandits, the learning goal of the learner is selecting one arm 2t E X in each round & E [T]: in order to minimize cumulative pseudo-regret:
R(T) = E. Σ T
cm (ri - -re)
(2)
where Tt is the reward of chosen arm ze; and rf is the reward of optimal arm कं, i.e. B|r]| = ha(0,) =
max ( hz(z).). (0)). Motivated by this learning objective, we formulate category reward definition below. " E.
Category Reward Formulation. In round t, we define the expected category reward E(re,e/ as the maximum expected reward among the arms within category E C. Let Ve, E Iele be category representation derived from contexts Xa. Then, with an unknown category-level mapping function lic(-), we formulate
Elrag]Aadt = hc((va) = ma(ee Blrc2]]
(1) = )))()))))
(3)
(8) where t²,, arg max 20 Exc. ha (x is the optimal arm in category c, and the expectation is taken over the random reward noise. Our specific instantiated formulation of category representations and their integration are detailed in Subsec.
Design Motivation for Category-level Reward. In round E [T], the learner aims to choose one arm 2, E Xg with the highost expected reward. Here, our category reward (Eq. 3 is designed such that selecting the best category oj C, naturally aligus with selecting the best arm sž, i.e., hec(Moz,)) maX h4(x))
max,ec, he
ha(x)). Thus, the target of the category-level model will naturally be choosing B arm categorics C, C C,, such that the highost-roward arms fall within them. This category-based formulation underpins our divide-and-conge
workflow, reducing the computational complexity to [((cc + Uuee, Xe, (), rather than O(K) in conventional neural bandit (e.g.. Zhou et al.) (2020): Zhang et al. (2021)). It also ensures close connection between category-level and arm-level models, which is crucial for theoretical analysis. On the other hand, alternative definitions (e.g., an average. category reward) can misalign with the goal of stochastic contextual bandits: choosing one optimal arm per round, as a high average reward does not necessarily indicate the presence of the best arm. Complementary discussions are shown in Appendix D
Notation. We apply vectors æ, v to denote arm context and category representation, respectively. C, denotes available arm categorics in round E [T], where cach c C, has arm collection Xe, C RR.. We aggregate candidate arms as X, = Ueec, Xe,-- For the category level, let C2 c G. denote selected categories. For the arm level, we have the chosen arm x, E Lr with X; = Uce Xr,t being the filtered candidate arms. For readers' convenience, we have also included a notation table in Appendix A
4 Proposed Framework
Overview of HyN-Bandit. Our pseudo-code provided in Algorithm 1 With the arm-category hierarchy, the category-level model is utilized to filter arm categories before the actual arm recommendation. Inspired by the neural adaptive exploration (Ban al.) 2022 Qi et al. 2023), we implement two neural networks 1C (:; O 1( trainable parameters. The estimated category rewards and the exploration scores are applied for category selection (lines 5-7, Algorithm effectivel narrowing down the entire pool of candidate arms, and significantly reducing computational costs. Subsequently, the arm-level neural model utilized to perform the precise arm recommendation (lines 8-11, Algorithm D.. Herc, we adopt the arm-level network fa(; Aa) for arm reward estimation with trainable parameters O A, and employ UCB-based exploration. After selecting one arm and obtaining its reward (lines 11 and 12, Algorithm
O (2)) to perform exploitation and exploration respectively, where Oc refer to their
we update the neural models with Gradient Descent (GD) (lines 12-16, Algorithm D. We leverage two exploration strategies to balance performance and computational efficiency. For the category-level model, where the number of choices is relatively small, we use an adaptive exploration strategy known for its strong performance (Ban et al. 2022 Qi al. 2023). For the more computationally demanding arm-level model, we adopt a relatively lightweight UCB-based approach, allowing us to leverage the performance benefits of bi-level exploration while maintaining overall efficiency.
4

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm Bi-level Hierarchical Neural Bandit (HzN-Bandit)
Input: Horizon T. GD iterations J. Learning rales I1c, 'IA- Exploration coefficient a. Regularization coefficient X. Number of selected arm categories B. Initialization: Initialize parameters ( lo: (0) and [O Initialize covariance matrix: Σg AL.
3: for each round & E [T]] do Receive available calegories C, and their arms Ce
First-stage (category-level) recommendation
5:
Derive the representation Ve,t for each arm category e e Ct. With category-level networks, calculate the overall score for each category c E Ct, denoted by FM (0c].-1) == fC (Me,si (0 It-1) + -ee (VSC I--1) Choose B arm categories C, argmax; &. CC E Fo(ue,t @0lc-i] with highest overall
6:
scores. Form the filtered candidate arm pool X = Ueeã, Ka,--
Second-stage (arm-level) recommendation for each filtered candidate arm a E X do
Calculate the reward estimation fA fa ( (e (le--)), and its UCB value UCB, (a!").
10:
end for Recommend 2; arg max (8) # E
(8) fa ( + UCB.(=
11:
> Updating Neural Bandit Models
12:
Receive reward and update arm-level model fA with GD. Update gradient covariance matrix
E, E. + g( (0a]-1)) g( (Q^]e-1)T/m.
13:
for each chosen arm category e E C. do
14: Record Merr, and its pseudo reward Fat min max
a 1 Mxx, (/(22)) (A))- + UCB. 1}.
15: end for
16: Train category-level models , with collected category representations and pseudo rewards.
17:
end for
4.1 First Level: Category-level Recommendation
Recall that each category e C, Vt E [T] corresponds to representation vector Me, to encode the information rogarding its associated arm collection Ke,.- In this work, we formulate the category representation as
Vatt
=.):: E 20 ENo.
Std Std(Xer) E Rdc
(4)
Ke,t
with [s being the concatenation operation, and naturally de = 2d. We recall that d is the context dimension. Here, given the arm collection X of category we have (t.( E IRd being the element-wis. standard deviation w.r.t. each element of the arm context vector (1() E X
Formulation Intuition of Category Representation. The intuition is that we need to encode the context spread for arm collection Xe, within the context space. Here, with the first d elements (the average arm context) representing the center context point, the second d elements in Mat (i.e., Std(Xc..)) formulate the interval around that mean point, in terms of each dimension within the context space. With the representation in Eq. we encode the given arm contexts Xe, as the dense hyper-ellipsoid. In this way, with a region that is proportional to this ellipsoid (c.g., according to the 30 rule), we can have each arm from Xe, falling into this uncertainty" principle
region with high probability. As result, motivated by the appiimssm-in-the-faccee AAbbasi- Yadkori al., 2011 Yang et al. 2020b), we utilize this design of the category representation provide sufficient information.

---

Published in Transactions on Machine Learning Research (01/2026)
4.1.1 Category Reward and Exploration Score Estimation.
With category reprosentation Ve,t; C E Ct, we apply category exploitation network (11) (:: (;))) to estimate the calegory reward (exploitation). It is also known that the confidence interval of reward estimation can be expressed as a function of the reward estimation model gradients (i.e., the gradients of exploitation network ((1) Ban et al. 2022 Zhou et al. 2020 Qi ct al. 2023). Therefore, to learn this relationship, we adopt a second category exploration network fo
(:: θ to calculate the exploration score for category E C.. This measures the 'potential gain', i.., Blrecl - fC (0)(( ( in terms of the category reward estimation. In this case, the input of exploration network f( will be the normalized gradient of the exploitation model: Vfc (vc,) == Vefé (vcz: (()), where we treat it as column vector for notation simplicity. The estimated exploration score is denoted by f6 (V (vo.):
Category Selection. We select top-B categories (line 7, Algorithm I with the highest overall scores (V
(Fo(Pe,; 0c)) eec, = (1
as the chosen arm categories C. Then, (())) (Ve.; o ! + ((2) (V (vc,): ? CEC,
the chosen categorics and their associated candidate arms & U.Eū. Ne, will be consequently applied for the arm-level recommendation in Subsec. 42
Remark 1 (Reducing Recommendation Complexity). For conventional stochastic neural bandit algorithms, the compulational cost is O(K), which can be significantly expensive as the learner needs to perform compula- tionally intensive principled exploration for every condidate arm. On the other hand, N.Ndiinn operates with the computational cost of O([Ce) + |Uee. Ke,e)) where |Ucež. Kext < K, |ccl < K, resulting in a significant reduction of complexily.
((2)) in terms of Category-level Neural Networks. Recall that we adopt two separate networks 16, .e.
exploitation and exploration respectively. Given the input calegory representation Vart E Bdd, LE (T), we first define the exploitation network ((1) to be FC network, with depth L 2 2 and width E N
f(V.,t: 2 )
(5)
where <(.) is ReLU activation, O E muxde θ E R 2 < < T, - A E R For notation simplicity, we denote its parameters as a column vector: @0 = |vec( (1)) vevv vee vr. and use e
(1), C l to represent the parameters @ after being trained by GD in t-th round.
Analogously, we also apply an L-layer FC network (with width m) to be the exploration network f& that can be similarly represented by Eq. 5 with the trainable parameters ( Note that the first-layer weight matrices between these two networks will have different shapes, since le is taking the network gradients
v (+) as the input instead. Similar to existing works (Ban et al. 2022 Qi et al. 2023). we apply average
pooling to the original gradient vector Vf(((.) (-) before feeding it into f(() in order to reduce both runtime
and space complexity. We adopt this method in HyN-Bandh for all experiments (Section 6
4.1.2 Efficient Category-level Training with Pseudo Rewards.
Recall that for category e E Cj its expected category reward defined as the highest expected arm reward within the category-specific arm pool Xe.t (Eq. 3. Consoquently, a key challenge the lack of access to true calegory rewards: we can only observe the reward r. for the chosen arm 2,, which may not be the best arm within the selected categories.
Pscudo Category Reward. To tackle this challenge, we know that the combination of reward point estimation (fa(w)) and the corresponding UCB (i.e., (x) from Eq. 7 can ofler an upper bound for the expected arm reward for an arbitrary arm æ with a high probability, based on derivations of our Theorem (Abbasi- (Abbasi-Yadkori et al. 2011), we use this upper bound as the "pseudo reward" r for training category-level models. This enables us to allocate the pewadd to each chosen category e E C,, thereby enriching the training samples for category-level
5.1 Inspired by the principle of
6

---

Published in Transactions on Machine Learning Research (01/2026)
networks. For each chosen category C2 and its candidate pool Xe,,, we define its clipped pseudo-reward
Fe,e min { 29 Ex [f (t) (All-1)) UCB. (2.1))
1. max
(6)
corresponding to line 14 of Algorithm The effectiveness of this formulation is supported by our theoretical analysis (Section 5) and experiments (Section 6 Note that, since arm reward estimates and UCBs are alrendy computed (lines 8- 10, Algorithm D we can directly reuse them to derive the category-leve pseudo-rewards without incurring additional computational costs.
Model Training. With collected category representations and pseudo rewards (Mar Ter F we
define the training loss for the exploitation network f8 as C (0) Eren Eneõ, |5 (,, -) Fer where the label is pseudo reward F. Meanwhile, since the input of the exploration network f(. is the gradients of fC we can utilize the previous gradients and the potential gain to train the exploration network. Thus, we formulate its loss: C (0) = Ere(s) Eeeū. 1 (V (ver): θ) (Fe,r - 5 (Ve,ri 1--)) and the label is 'potential gain' F - (1) (a)). With the loss functions above, we run Gradient Descent for J iterations to update networks f( and f( given the learning rate no (line 16, Algorithm
4.2 Second Level: Arm-level Recommendation
Next, with the chosen categories & C Ct, we need to recommend one arm a, E & from the filtered candidate arms X U..ë Ke, accordingly.
Arm Reward Estimation and UCB. Given an arm æ, we apply the arm-level neural network fa(: A.)) to estimate its reward, and the reward estimation will naturally be the network output fa x). To achieve arm-level exploration, we apply UCB-based strategy reduce the computational cost. Given probability constant 8 (0, 1), we aim to formulate the UCB, such that P(ISA(#;; a ha(2)) (a)) s 6, for each arm æ E Ny. Based on NTK norm S > 0 and the confidence ellipsoid derivations from Theorem 5.1 with the probability at least - 6, we have
UCBa(x)= - -0(a)) (0/ log det(AI)
det ( 2 log(() + x1/3)) |9((;; 10ll--)/
where the covariance matrix E,-1= AI Ereng (9A)-1)))) g( (9A)=1))))) /m/, with the regularization coefficient > 0. Recall that in Eq. [ a represents the variance proxy. If this value is the unknown prior, we can treat a 2 0 as tunable coefficient controlling exploration intensity, as in existing works (Zhou et al.
2020 Zhang et al. 2021
Arm Selection. Using reward estimation, along with the UCB scores and exploration coefficient a, we recommend arm æ,, with the highest overall score from the candidate pool X, (line 11, Algorithm
at = arg max MeT [f ( ①A) + (a!.)
Upon the selection of arm æt, its actual reward rt will be revealed, following the stochastic bandit settings.
Arm-level Neural Network and Training. Similar to category-level models (Eq. 5) we also adopt L-layer FC network for reward estimation: fa(æ; + == 0 0",0(''__1000'________
O(O x))), with the hidden dimension m. Note that the input of fA will be the arm contexts with dimensionality d. Therefore, the shape of the weight matrix in SA's 's first layer would be Ø E mdd Analogous to category-level model, O = (vec(())).vec((())) vec(OO)T,,....... vec) TJT e RP* represents the trainable parameters. We also update fA via Gradient Descent (line 12, Algorithm D] With the chosen arms and their rewards (ar,Tr)rei) up to round t,
we define the quadratic loss function with regularization LA( - Erei [ ))-r,(
md
1 0
2
Then, we perform the Gradient Descent for J iterations, with learning rale 7/ 0.
7

---

Published in Transactions on Machine Learning Research (01/2026)
5 Theoretical Analysis
Theoretical Contributions. First, we establish the regret analysis for hierarchical stochastic neural bandit
without. assuming specific reward-mapping priors (e.g., Hong el al. (2022); Zuo et. al. 2022) Aouali el al. (023); Yang et al. (2200a); Sen et al. (2021)), ), allowing arbitrary arm reward functions for greater generality.
Second, wC propose a novel pipoline to address the challenge of the absence of true category-level rewards. By leveraging pseudo-rewards derived from the arm-level model, we ensure joint optimization of the bi-level models while maintaining theoretical guarantees. Third, we develop a novel theoretical proof framework for our two-level exploration strategy; where category-level neural exploration refines arm candidate pool, before arm-level UCB optimizes action choice, ensuring balance between efficiency and performance. Fourth, unlike prior works with arm separaleness assumptions (e-g-, Zhou et al. (2020); Zhang et al. (2021): ; Ban et al. (2021 2022)), ) we integrate novel confidence ellipsoids with martingale- based analysis to enable our regret analysis, without relying on such assumptions. Finally, with a general regret bound in Theorem 5.1 Theorem 5.2 can further tighten the bound under a mild 'category margin' condition, highlighting the effectiveness of our category-level filtering and bi-level formulation.
5.1 Preliminaries for Theoretical Analysis
Inspired by Zhou et al. 2020); Allen-Zhn et al. (2019), for initializing category-level fC and fo we draw each entry of O,, Vi E [L II, from the Gaussian distribution A/ 2/m); each entry of O2 is drawn from (O, 1/m). For the arm-level model fA. we sample the entries of its intermediate weight matrices 0%,1 E [Z-
- 1] from (/, 4/m), while sampling the entries of Ø' from Gaussian distribution N 20,2mm)
Analogous to Zhou et al. (020):
Zhang et al.
(2021); Ban et al. (0022)
et al.
2023
2024
consider
unit-length arm contexts I (1ll
1, [Kot). c C., E [T].
Without loss of generality, we apply a
normalization process inspired by Allen-Zhu al. (0019) Zhou et al.
2020 Jia al.
(002 Qi et al. 2024
with umprocessed a((), the corresponding normalized arm context will be x
1
2-11
We consequently have: (i) | ll2 = 1; (ii) no two normalized arm contexts will be in opposite directions; (6)
and (iii) SA [a( AAl))) = with randomly initialized parameters AO
D NTK Gram Matrices. Let क; = arg max ma nec, Xx.,) h(x)) be the "best possible chosen" arm from
chosen categories C, E [T], along with the chosen arms ( and optimal arms {xt herr where xf
arg max (9 h= (1) Then, we simply merge these three arm collections as Ar with cardinality |Ar| 37,
which can possibly contain duplicate arms. Meanwhile, we define Ar == (f U ( hee(T] U { { (T)(T))
as the union set; and consequently, Ar will only contain unique arms from Ar, S.L. [r < | = 37.
Definition 1 (NTK Gram Matrix with Possibly Duplicate Arms (Jacot et al. 2018 Zhou et al. 2020 ). Let N denote the Gaussian distribution. With ReLU activation o(-) and its derivative o' d'(-, define following recursive process. For I E [L] and i,j E (Ar(..,|AAII, with MD = b = (I,, x,), let
No. w/,, Vis v', ),y)
f/j 2E N, (o(o) (b)), M = 2M! N. " (o'())
Given orm collection Ar (|AT] = 3T) with possibly duplicate arms, define ils NTK Gram Matriz M = (M- + 2/2 E 13Tx3T
Definition 2 (NTK Gram Matrix with Unique Arms) Follow the recursive process in Def. 1 For arm set AT with unique arms, define its NTK matrix M (M' + a 1)2 e BlAr x xlrrl, where |rr S |Arl.
Remark 2. (Removing Arm Separoteness Assumption) Most neural bandit works generally adopt arm separateness assumptions, e.g-, Zhou al.) (2020); Zhang al. (022): Ban et al. (2021); Dai al.) (2023); Xu et al. (2020) assume minimun NTK matria eigenvalue An > 0: Ban et al. (2022) Qi al. (2023) assume the Euclidean seporateness: || x'1/2 for any two observed condidate arms x, x!. They can be easily
8

---

Published in Transactions on Machine Learning Research (01/2026)
violated when we have duplicate arm contezts. Inspired by Qi ct al. (2024), we integrate refined confidence ellipsoids with our novel martingale-base analysis to derive regrel bounds withoul seporaleness assumplions, enabling joint optimization of our bi-level models with two different exploration mechanisms.
Definition 3 (NTK Matrix Effective Dimension (Valko et al., 2013 Zhou et al. 2020 Zhang et al. 2021 ct al. 2024g) Given horizon T, regularization coefficient X (Eq. 7. and NTK matrir M, define effective
dimension d of matriz M d = log det (M/A)) with respect to arm collection AT with |Arl = 3T'
log [TT(/)
5.2 Regret Analysis
We also would like to mention that our theoretical analysis results can also be readily generalized other types of neural architectures, such as Convolutional Neural Networks (CNNs) and ResNet with over-parameteriattin Allen-Zhu et al. 2019 Cao & Gu 2019 Next, we present the main regret analysis result in Theorem 5.1 considering both category-level and arm-level error.
Theorem 5.1. Given the finăte horizon T, for any 8 E (0,1) and given X, ER > O, suppose width m 2 ((polyyTT, L, R2 " KÊR log(1/8)), ne vm UA O(TTL + mA)-1), 2 Ö(TL/A). Let Sc .SC and SA be the I.-layer FC networks with width m. Then, H2 N-Badil achieves the regret bound
R²
R(T) S (V ( dlog(1 + TK/A) +log())+(Vs))) VAS)) + +O(TTlog(1/0) + VER) + 0(1),
with probability at least 1 d over the random initialization.
The proof is presented in Appendix L Despite the category-level recommendation we applied to reduce the computational cost, our regret bound is comparable with stato-of-tho-ar results in neural bandit works (Zhoul
et al.
2020 Zhang et al. 2021 Ban et al. 2021 Jia et al. 2022 Qi et al. 2022] with overall regret of Odd ()..T). T). Our NTK Gram matrices (Defs.
depend on at most 37 arms, different from prior works (e.g., Zhou et al. (2020); Zhang al. (2021) that rely on all TK candidate arms X, E [7], leading
compact definition of effective dimension d. In addition, our parameter norm S can be tighter than in prior works (e.g., Zhang et al. ): Zhou et al. (2020)), as our confidence ellipsoid around O, only needs hold for arms in collection Ar (|Arl S 37), rather than all the TK observed candidate arms.
5.3 Category-level Recommendation Analysis
Different from the Subsection 5.2 above, for the next Theorem 5.2 we instead consider settings analogous to those in existing works (Qi et al. 2022 Ban al. (022), where candidate arms X, are sampled i.i.d. from a context distribution. Meanwhile, we also suppose that the expected category rewards satisfy mild ç-margin condition below, to ensure their separability and facilitate stronger theoretical results. That ís, with the optimal category ct = arg maxcec, (Kc,),)) and second-optimal category c = arg maxee(C, he we suppose there exist a constant Ç 0, s.t. |B]re [Xc,ta Elreg,//Ke 2 <, with notation from Eq, 3 Note that there can be multiple optimal second-optimal categories with identical expected rewards respectively. As long there is gap { between the rewards of the optimal and second-optimal category(-ies). i.e., not all arm categories have the same expected reward, this mild condition will consequently hold.
Theorem 5.2. Suppose fC ((()) are L-layer FC networks with width m. Let m. L, ne satisfy the conditions in Theorem 5.1 Suppose Hg N-Baddil chooses B calegories in each round t. Then, given the calegory margin 0, with the notation from Theorem 5.1 and Algorithm 1 when round t satisfies
Ölay x 2glog(0) SV SV Xd) + O ((Voog(o-1) VER)
12 T
B.C
the optimal arm category of = arg maNcec, (v(,,.) is assured to be selected by the category-level model (t.e., ct E EC.) with probability at least 1 8-8.
The proof is presented in Appendix According to Theorem 5.2 when 2 T, H,N-Bandit is guaranteed
choose the optimal arm category with high probability, where will consequently have zero 'category-level'
9

---

Published in Transactions on Machine Learning Research (01/2026)
error. Thus, for the second O term on the RHS of Theorem 5.1 that corresponds to the category-level error, we can replace the finite horizon T term with the Tiin = min (T.7) 7) based on Theorem 5.2 and it can lead to the alternative regret bound of R(T)= S O(dVT) data-dependent, decreasing with smaller effective dimension d and NTK norm S. More categories chosen (i.e., larger B values) can also reduce T by increasing the likelihood of selecting the optimal category.
O(TTmin 1og(6-1) + <TiinRR). Here, T is
6 Experiments
We conduct experiments on three real-world data sets with varying specifications. Meanwhile, our nine baseline algorithms are: (1) Linear algorithms: Lin- UCB (Li et al. 2010 Lin- ACn-UCB-CI CCCBBCCaegoryy {Li et al.
2010); (2) Kernelized algorithms: Kernel-UCB (Valko et al. (013), KMTI-UCC (Deshmukh et al.
2017 Kernel-UCB--mn Ind (Deshmukh al.) 2017); and (3) Neural algorithms with principled exploration:
Seural-UCB (Zhou et al. 2020), Neural- UCT-al-UUB-C Cattaeory (Zou et al. 2020). Neural-TS (Zhang et al., 2021)
Net (Ban et al. 2022). Here, Lin-UCB-Categonn
extend Linear-UCB (Chu 2011) and Neural-UCB (Zhou et al., 2020) respectively, by incorporating category-aware embeddings iQi et al. 2022), allowing them to also leverage arm category information. Kernel-UCB--nu refers to Kernel- UCB (Valko et al., 2013) under the disjoint setting (Li et al., 2010), where individual estimators are learned for each arm category. Detailed descriptions and source code link are provided in Appendix [B.
and Neural-UCB-Catee
ct al.
6.1 Experiment Results on Three Real Data Sets
MovicLens and Yclp Data Sets. Our first data set is MovicLens-2001 (Harper & Konstan 2015 With
genome-scores of user-specified lags, we choose the top 20 lags with the highest genome-score variance to create the movie features p E Rd (d'= 20). The movies are classified into 19 categories based on their
genres: [C] = 19. We then obtain user fcatures u E Rd following existing works (Li et al., 2019, Ban et al.
2022
Qi et al. 2022 2023), by applying singular value decomposition (SVD) to the user-movie interaction
matrix. Then, 5,000 movies and 10,000 users with the most reviews are applied following existing works
(e.g., Li et al. (2019)) With a user u, sampled from the 10,000 users at each time step t, we follow the idea
of Generalized Matrix Factorization (GMF) (He et al., 2017 Zhou et al., 2021 to encode user information and i-th item into the arm context through concatenation Te, = [Mm, P
,ce Ct, i E [Kat], and let sampled arm pool size K | 1,000. We then append constant of 0.01 to x!!) to obtain x!{) e Rd before applying L2 normalization. Such procedure leads to context dimensionality d = 41. Arm rewards (0) are user ratings normalized into range [0, 1]. For Yelp data set (https://www) yelp. saslp.ccm. wwt dattsett,,,),, SVD is analogously applied to extract user and item features with a hidden dimension of d' = 20. Then, we apply 10,000 users and 4,000 restaurants from 20 categories ((C) = 20) with the highest number of reviews for candidate selection. We then apply the above GMF procodure to obtain arm contexts (1()) E X2 C IRd (d = 41, X = 1,000), incorporating user and item information. Arm rewards are user ratings normalized to [0, 1].
E 2d
Amazon Data Set. For Amazon recommendation data set (He & McAuley 2016), we select the items from C|= 10 categories, and cach user-item pair (arm) is associated with a review and corrosponding rating. To derive the arm context, we transform the review text into vector representations, by following the same text processing procedure outlined in the "Sentires' package (Zhang et al. 2014 Li et al. 2020). The obtained arm context maintains a dimensionality of d = 41, with the L2 normalization applied on arm contexts. Similar to the Yelp and MovieLens data sets, we let |&| = 1,000 in each round, by sampling from transformed user-item pairs (each treated as an arm); and we define the unknown arm reward as the normalized user rating scaled to range [0, 1). Complementary details are presented in Appendix B.1
Main Results. On the left side of Fig. [ HşN-Bandis consistently outperforms all these strong baselines. The standard deviation of HşN-Bandit is also plotted as the red shaded area. Among these baselines, the neural algorithms (Neural-UCB, EE-Net, Neural-TS) tend to outperform lincar and kernel algorithms, due to the representation power of neural networks. In addition, by leveraging the calegory information, Neural- Cirral-UB--CA CCaBeCCtteoryy (Neu-Cat.) achieves better performance compared with the original Neural-UCB: on the MovieLens and Yelp data sets. In contrast, Lincar- -Cherr-UBB-CA CatC--Cayggryyy (Lin-UCB-Cat. generally performs worse than the original Lin-UCB, This performance discrepancy is observed because the discrimination power of linear models is limited, and they can possibly fail to learn the underlying mapping as well as effectively
10

---

Published in Transactions on Machine Learning Research (01/2026)
5045
Macgeirpe
6:1
Amazen
3044
2
4000
$.000
2423
342
1330
2001
2033
umn
1010
1000
3043
2230
1000
22.0
2000 120 6539
side 1000e
303
655 463
182 13803
2002
455 400
180 23003
3000
Ramin Trm
Li-ats
KHTL-UCH
1E-Nvo
Neu-15 Nau-Cat
LnNUCIS-CM Bandt
Lan4uCh
IXTTL-UXI
EL-Me::
Neu-75 Neu-Car.
KerUCGa
Kanled
MeG-UCB
KenUCB
forind
NeurUGB
H #.dl-Baddt
Figure 1: [Left Figure] Regret results on three recommendation data sets. Right Figure] Regret vs. Rumning Time (Linear basclines symbols: o; Kernel baselines: A; Neural basclines: D H2N-Bandit: *).
leverage the category information encoded. Compared with Neura--UCT--Catgoory,, this observation further supports the notion that neural methods are better-suited solutions for utilizing available category information. Meanwhile, Carnel-UCB-Ind (Ker-Ind), which learns individual kernelized models for each category, suffers from the data sparsity issue and exhibits the worst performance among all the baselines. Our N-N-Bandit outperforms the basclines by effectively balancing the category-lovel and arm-level explotattion-ccploratinn Meanwhile, H2N-Bandit can take as little as 1/3 of the rumning time of other neural algorithms, which need to enumerate all the candidate arms for arm-level exploration. In addition, in Subsec. 6.4 empirically demonstrate that H2N-Bandit can also be extended to three-level arm hicrarchy settings, which results in enhanced computational efficiency with only moderate performance degradation. This demonstrates the compatibility and scalability of our H2 H-N-Bandit. framework, enabling practitioners to determine the specific arm hierarchy based on their own application scenarios and data set characteristics, in order to strike a good balance between computational costs and model performance.
Performance vs. Rumning Time. On the right side of Fig. we compare with baselines regarding the model performance and running time. Each colored dot represents in the lower left region are considered better in terms of both the running time and model performance. From the results, HyN-Bandit achieves superior performance when compared to other baselines. Notably, HyN-Bandit achieves competitive performance in terms of cumulative regret while requiring only one-third of the rumning time of Neural-UCB. This aligns with our claim that category-level recommendation can strike a good balance between the model performance and the computational cost. Furthermore, the kernelized methods also suffer from the high computational cost issue, because the kernel evaluation has to be performed between all the candidate arms and the past chosen arms, which can be extremely time-consuming.
method, where the methods (dots)
6.2 Category-level Recommendation Analysis
Recall HgN-Bandi applies networks (.),))))))))))))))))))))))))))) to balance exploitation and exploration in category-level recommendations. We further analyze its category- level exploration behavior on the Yelp data set.
(Amarr thew manip fine 26 mundi
Fure Eea keaoed
0.175
Amarican
600-
Asian Fusion
+27.%%
0.150
Breakfast
0.125
Salad
Nightli'e
400
0.100
japanese
In the left figure of Fig. 2 we compare the category exploration scores (i.e., outputs of ((2)) ) for six specific arm categories. At round 2,000, N-N-din actively explores major categories like 'American' restaurants, which have more arms and user interactions than mi- nor categories such as "Japanese." Early in the rec- ommendation process, this helps N- build strong global understanding for high-quality recom- mendations. By round 9,000, exploration scores shift toward minor categories, as major categories have al- ready been sufficiently explored. Notably, the "Asian' category receives a negative score, since ((2) can produce negative values. This indicates HyN-Bande is compensating for overly high estimated rewards that category, encouraging exploration of underrepresented categories for complementary information. Additionally, the average exploration score decreases over time, the system gathers more interactions from the environment, gradually favoring exploitation. On the
10:2
0.050
200
0.015
4:1
100-
0.000
2000 Nound
5005 Hlund
Bandi
Manu UCC
Figure Exploration results on Yelp Data set. [Left: Figure] The category-level exploration score change from 2000 round to 9000 round. [Right Figure] Ex- ploration cumulative reward comparison showcasing the benefit of our category-level filtration.
11

---

Published in Transactions on Machine Learning Research (01/2026)
3007
Medda SpANge
2010
1400
30.0
2300
E200
22.0
2560
15
2300
3000
275
1000
1000
540
200
6300
1000
2003
ado 18930
3009
Tra
1000
<or UCB
EE/NcC Now-UCs
NS
HyN- -Bnoit
EC-Nie
New-TS
ONTL-UC
Cat.
NyN Sanatt (3 leve))
KMTL-UCS
Neauca
Neu-Catt
15W Dannat 13 lnowa))
Figure 3: Regret (left three figures) and running time comparison (right three figures) for threo-level
HgN-Bandit, [Kernel baselines: A Neural baselines:
D HgN-Bandi and HyN-Bandi (3 levels): *].
Data set
==2
B ==4
B =
B ==8
Data set
a=
==
0.1
0.3
0.5
No Cat. Exp.
Yelp
3354 20622.0
3077
3159
296 1608
Yelp Amazon
3212+xa
3128
3077+41
3253
3345a2
Amazon
1623
1753
1809
1623+42
1658*23
1653#47
1761+27
Table 1: Regret w.r.t. chosen category quantity B
Table 2: Regret w.r.t exploration coefficients
right side of Fig. 2 we compare with Neural-UCB in terms of exploration quality. Different from line 11
in Algorithm 1 we alternatively choose arm F,, E [T] with 'pure exploration', by only using the UCB:
arg max (+) ExG [=] where X, = Ucee Xe,-- Similarly, Neural-UCB will select arms solely
based on UCB valuos. As H₂N-Bandi achieves higher cumulative reward, its category-level recommendation
contributes to improved exploration quality.
6.3 Parameter Study
Next, we present parameter study for the number of selected categories, B in Table [ where the effect of B is task-dependent. For the Yelp data set (20 total categories), a larger B can improve performance by increasing the chance of selecting the optimal category, but we find B = 4 offers good tradc-off with computational cost. In rost.ast. for the Amazon data set (10 calegories), a larger B does not necessarily improve and can degrade performance by reducing filtering effectiveness, leading to unnecessary arm-level exploration. Thus, practitioners can tune B starting from smaller values to balance performance and efficiency.
Empirical results with different exploration coefficient a are in Table 2 where setting or E [0.1, generally achieves satisfactory performance. It is worth noting that both exploration (a = 0) and excessively high exploration can negatively impact model performance. HzN-Bandit, equipped with category-level exploration and a modest level of arm-level exploration, can effectively support arm recommendation. In addition, include results for the setting with no category-level exploration by disabling fe. ,(2) demonstrating that
equipping H2N-Bandit with category-level exploration is essential for achieving optimal performance.
6.4 Extension: Adapting H₂N- Bandit to a Three-Level Arm Hierarchy
We also extend H-N- Bandit to three-level hierarchy (byper-category, category, and arm), by grouping existing categories into three handle this structure, we introduce an additional hyper-category model analogous to our original category-level model; it uses similar neural architecture, derives representations as in Eq. 4 and is trained on pseudo-labels generated by the category-level networks. The recommendation becomes a three-stage filtering process from hyper-category down to the final arm. We let |& = 1,000, t E [T], and compare with kernelized and neural baselines from Subsec. 6.1 Complementary details of the experimental settings are Appendix B.2
using K-means clustering on their mean contexts. To
Based on the three line charts at the left of Fig, incorporating third-level (lyper-categorp-leeee) model generally results in slight performance degradation in terms of cumulative regret across the three real data sets. For the Yelp data set, HyN-Bandit (3 levels) is able to outperform kernel-based baselines and maintain comparable or close performance relative to strong neural basclines (c.g., Neural-UCB and Neural-TS). However, for the remaining two data sets, MovieLens and Amazon, its performance tends to be slightly inferior to these neural baselines. Regarding the running time results, HęN-Bande (3 levels) improves the efficiency of the two-level HyN-Bandit by significantly reducing the number of candidate arms for arm-level selection through the hyper-category--lee filtering. This demonstrates trade-off between model performance and computational efficiency in terms of arm hierarchy levels. While HyN-Bandit, (3 levels) achieves the
12

---

Published in Transactions on Machine Learning Research (01/2026)
shortest running time, proposed HyN-Bandit (2 levels, Algorithm ! can help strike better balance between model performance and computational cost.
7 Conclusion
We propose novel neural bandit framework, HyN-Bandit, to leverage the available category information in recommendation. It utilizes the bi-level hierarchical neural structure to tackle online recommendation tasks, along with principled exploration strategies to address the ssplottation-exploattiie dilemma. By leveraging category-level recommendation,, HzN--Baddit can significantly reduce the computational cost by filtering the arms based on their categories, while simultancously improving the arm-level recommendation. Under standard neural bandit assumptions and per-pparameteriee neural network settings, we perform regret analysis and provide the performance guarantee for the category-level recommendation. Extensive experiments are conducted to show the effectiveness of HyN-Bandit against strong baselines, and the behaviors of HyN-Bandit in terms of running time and category-leva recommendation.
Acknowledgments
This work is supported by National Science Foundation under Award No. IIS-2117902. The views and conclusions are those of the authors and should not be interpreted as representing the official policies of the funding agencies or the government.
References
Yasin Abbasi- Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-200 2320,, 2011.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payofis. In ICML, pp. 127-135. PMLR, 2013.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 222-522, PMLR, 2019.
Imad Aouali, Branislav Kveton, and Sumeet Katariya. Mixed-effect thompson sampling. In International Conference on Artificial Intelligence and Statistics, pp. 2087-2115. PMLR, 2023.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint 1rXit:1904.11950 2019.
Peter Auer, Nicolo Cesa- Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47 22223)):235-25 256, 2002.
Yikun Ban and Jingrui He. Convolutional neural bandit: Provable algorithm for visual-aware advertising. arXiv preprint orXiv:2107.07555 2021a.
Yikun Ban and Jingrui He. Local clustering in contextual multi-armon armed bandits. In Proceedings of the Web Conference 2021, pp. 2335-2346. 2346, 2021b.
Yikun Ban, Jingrui He, and Curtiss B Cook. Multi-facet contextual bandits: A neural network perspective. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 35-45, 2021.
Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Fe-net: Expllitaation-exxlrraaii neural networks in contextual bandits. In International Conference on Learning Representations, 2022.
Yikun Ban, Yunzhe Qi, Tianxin Wei, Lihui Liu, and Jingrui Hc. Meta clustering of neural bandits. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 95-106, 2024.
13

---

Published in Transactions on Machine Learning Research (01/2026)
Renqin Cai, Jibang Wu, Aidan San, Chong Wang, and Hongning Wang. Category-aware collaborative sequential recommendation. In Proceedings of the 44th international ACM SIGTR conference on research and development in information retrieval, pp. 388 397, 2021.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 32:10836-10846, 2019.
Nicolo Cesa-Bianchi, Claudio Gentile, and Giovanni Zappella. A gang of bandits. In NewrlPS, pp. 737 745, 2013.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In AISTATS, pp. 208 204, 2011.
Zhongxiang Dai, Yao Shu, Arun Verma, Flint Xiaofeng Fan, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated neural bandits. In The Eleventh International Conference on Learning Representations, 2023. URL https://openrevierz
Aniket Anand Deshmukh,, Urun Dogan, and Clay Scott. Multi-Lask learning for contextual bandits. In NeurIPS, pp. 4848 4856, 2017.
Audrey Durand, Charis Achilleos, Demetris lacovides, Katerina Strati, Georgios D) Mitsis, and Joelle Pineau. Contextual bandits for adapting treatment in mouse model of de novo carcinogenesis. In Machine learning for healthcare conference, pp. 67 82. PMLR, 2018.
Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering of bandits. In ICML, pp. 757-765, 2014.
Claudio Gentile, Shuai Li, Purushottam Kar, Alexandros Karatzoglon, Giovanni Zappella, and Evans Etrue. On context-dependent clustering of bandits. In ICML, pp. 1253- 2017.
Quanquan Gu, Amin Karbasi, Khashayar Khosravi, Vahab Mirrokni, and Dongruo Zhou. Batched neural bandits. ACM/JMS Journal of Data Science, 1(1):1-18, 2024.
F Maxwell Harper and Joseph A Konstan. The moviclens datasets: History and context. Acm transactions interactive intelligent systems (liis) 5(4):1 19, 2015.
Ruining He and Julian McAuley. Ups and downs: Modeling the visual evolution fashion trends with one-class collaborative filtering. In proceedings of the 25th international conference on world wide web, pp. 507-517, 2016.
Ruining He, Charles Packer, and Julian McAuley. Learning compatibility across categories for heterogeneous item recommendation. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 937-942. IEEE, 2016.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In WWW, pp. 173 182, 2017.
Joey Hong, Branislav Kveton, Sumeet Katariya, Manzil Zaheer, and Mohammad Ghavamzadeh. Deep hicrarchy in bandits. In International Conference on Machine Learning, pp. 8833-8851. PMLR, 2022.
Liang Hu, Jian Cao, Guandong Xu, Longbing Cao, Zhiping Gu, and Can Zhu. Personalized recommendation via cross-domain triadic factorization. In Proceedings of the 22nd international conference on World Wide Web, pp. 595 606, 2013.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Yiling Jia, Weitong Zhang, Dongruo Zhou, Quanquan Gu, and Hongning Wang. Learning neural contextual
bandits through perturbed rewards. In International Conference on Learning Representations, 2022. URL
14

---

Published in Transactions on Machine Learning Research (01/2026)
Parnian Kassraie and Andreas Krause. Neural contextual bandits without regret. In International Conference on Artificial Intelligence and Stalislics, pp. 240-278, PMT.R, 2022.
Andreas Krause and Cheng Soon Ong. Contextual gaussian process bandit optimization. In NewrIPS, pp. 2011.
Lei Li, Yongfeng Zhang, and Li Chen. Generate neural template explanations for recommendation. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 755-764, 2020.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personalized news article recommendation. In WWW, pp. 661 670, 2010.
Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased offline evaluation of contextual- based news article recommendation algorithms. In Proceedings of the fourth ACM international conference on Web search and data mining, pp. 297-306, 2011.
Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. In SIGIR, pp. 539 548, 2016.
Shuai Li, Wei Chen, Shuai Li, and Kwong-Sak Leung. Improved algorithm on online clustering of bandits. In IJCA, pp. 2923-29222 2929, 2019.
Carl D Meyer. Malris analysis and applied linear algebra, volume 71. SIAM, 2000.
Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi,, Xiuyuan Lu, and Benjamin Van Roy. Approximate thompson sampling via epistemic neural networks. In Uncertainty in Artificial Intelligence, pp. 1586-1595. PMLR, 2023.
Yunzhe Qi, Yikun Ban, and Jingrui He. Neural bandit with arm group graph. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1379-1389, 2022.
Yunzhe Qi, Yikun Ban, and Jingrui He. Graph neural bandits. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, pp. 1920 1931, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701030. doi: 10. 011445/5550355359937777 URL https://doi.
10. 1tte//11.111//588800 359953777330339331111
Yunzhe Qi, Yikun Ban, Arindam Banerjee, and Jingrui He. Robust neural contextual bandit against adversarial corruptions. In The Thirty-eighth Anruaa Conference on Neural Information Processing Systems, 2024.
Rajat Sen, Alexander Rakhlin, Lexing Ying, Rahul Kidambi, Dean Foster, Daniel N Hill, and Inderjit S Dhillon. Top-k extreme contextual bandits with arm hierarchy. In Internationol Conference on Machine Learning, pp. 9422 9433. PMLR, 2021.
Zhiyuan Su, Sunhao Dai, and Xiao Zhang. Revisiting clustering neural bandits: Selective reinitialization for mitigating loss of plasticity. arXiv preprint arXiv:2506. 12389, 2025.
Michal Valko, Nathan Korda, Rémi Munos, Taas Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Uncertainly in Artificial Intelligence 2013.
Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual bandits in a collaborative environment. In SIGIR, pp. 529 538, 2016.
Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint XrXiv:2012.01 00100000,,, 2020.
Mengyue Yang, Qingyang Li, Zhiwei Qin, and Jieping Ye. Hierarchical adaptive contextual bandits for resource constraint based recommendation. In Proceedings of the web conference 2020, pp. 292 292-302, 2020a.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan. On function approximation in reinforcement learning: Optimism in the face of large state spaces. arxic preprint arXiv:201 00t:2011004000 1.06622, 2020b.
15

---

Published in Transactions on Machine Learning Research (01/2026)
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference on Learning Representalions, 2021.
Yongfeng Zhang, Haochen Zhang, Min Zhang, Yiqun Liu, and Shaoping Ma. Do users rate or review? boost phrase-level sentiment labeling with review-level sentiment, classification. In Proceedings of the 37th international ACM SIGIR conference on Research & development in information retricval, pp. 1027-1030, 2014.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ueb-based exploration. In International Conference on Machine Learning, pp. 11492-1111 11502. PMLR, 2020.
Yao Zhou, Jianpeng Xu, Jun Wu, Zeinab Taghavi, Evren Korpeoglu, Achan Kannan, and Jingrui He. Pure: Positive-unlaeeled recommendation with generative adversarial network. In KDD, 2021.
Feng Zhu, Yan Wang, Chaochao Chen, Jun Zhou, Longfei Li, and Guanfeng Liu. Cross-domain recommenda- tion: challenges, progress, and prospects. arXiv preprint 0rXiv:2103.01696, 2021.
Zheqing Zhu and Benjamin Van Roy. Scalable neural contextual bandit for recommender systems. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp- 3636 3646, 2023a.
Zheqing Zhu and Benjamin Van Roy. Deep exploration for recommendation systems. In Proceedings of the 17th ACM Conference on Recommender Systems, pp. 963 (83-970, 2023b.
Jinhang Zuo, Songwen Hu, Tong Yu, Shuai Li, Handong Zhao, and Carlee Joe-Wong. Hierarchical conversa- tional preference elicitation with bandit feedback. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp. 2827 2836, 2022.
16

---

Published in Transactions on Machine Learning Research (01/2026)
Broader Impact Statement
This paper introduces HzN-Bandit, a novel hierarchical framework that advances neural contextual bandits by making principled exploration computationally efficient. for large-scale online recommendation.. This enhancement improves the utility and performance of such systems by intelligently leveraging category-level do not foresce significant negative impacts. Potential
information. While work has broad applications, concerns, such as the amplification of biases present in the data, are general to the field of recommender systems and not uniquely introduced by our method.
A Notation Table
In this section, to enhance the readability of readers, we include table for the notation along with the corresponding descriptions.
Notation Deseription Table
Notation
Description
Notation
Deseription
Finite horizon
Total number caudidate arms in each round Number selected arm categories
context
B
Calegory representation
R(T)
Cumulative peeudo-regrel for T rounds Network depth number of layers Network width number of hidden units NTK Gram matrix with possibly duplicate arms NTK Gram matrix with non-duplicate Regularization coefficient
Reward
L
Arm context dimension
de
Category representation dimension
M
Ar
Arm collections / sel for optimal and closse
M
Collection of all categories
C
Received categories collection (in round 8)
Reward random noise
C,
Selected eategories collection (in rund f)
Exploration coefficient
X
Collection of all candidate arms (in round t)
Number of iterations for GD Minimom eigenvaiue of the NTK matrix M Learning radius for category-leve model Regression difficulty with radius NTK norm parameter
Xaa
Candidute from eategory (in round
A
X
Candidate arms from selected categorics C2 (in round f)
R
Mapping funetion for reward
Cx
Mapping function for category zeward
fo (
Category-leve exploitation network
Prohahility parameter
Category-level explorstion network
Category-level learning rate
Fe()
Shorthand extegory overall score (() + (2)
Arm Arm-level learning
Arm-level reward estination network
Gradieut covariance matrix
Trainable network parameters
0(:0) ()
Vector of network gradients w.r.t. parameters
[})
Network parameters trained by f-th round GD
C(-)
Loss function
Table 3: Notation Table
B Experiment Details and Complementary Experiments
B.1
Experiment Details
Here, for all the UCB-based baselines, choose their exploration parameter from the range {0.01, 0.1,
with grid search. Following experiment settings from the original papers of our baselines (Zhou et al. 2020 Zhang et al.) 2021 Ban et al.] 2022), we set the number of layers L = 2 for all the deep learning models including our proposed HyN-Bandle We also set the network width with grid search m E (100, 200, 300)- The learning rate of all neural algorithms are selected by grid search from the range {0.0001, 0.001, 0.01}. For all the algorithms, we choose the regularization parameter X from the range (0.0001, 0.001, 0.013. Then, we choose the exploration coefficient from the value range {0.2, 0.5, 1} for HęN-Bandit in terms of scaling, For kernelized basclines, apply the radial basis function (RBF) kernel, and choose the kernel bandwidth from {0.01, 0.1, 1}. All experiments are performed on server with Intel Xeon CPU and NVIDIA V100 GPUs. The results are based on the experiments across 3 runs.
Here, we would like to add the URLs for the data sets and the data processing package applicd in the experiments:
'Qur code usp=sharing
available: http:h//w....cccc.oo.oooooo/oota
17

---

Published in Transactions on Machine Learning Research (01/2026)
MovieLens data set: http:://ggooolaa.ooo///aaaaaaaaa
Yelp Review data set: http://www..eel..com//aaaaa
Amazon data set:
Sentires package for processing the Amazon data set: Sentires-Guide
https://gttabb.co//lleiiisse
In addition, we also would like to include more detailed descriptions for our nine baseline algorithms:
Lin-UCB represents Linear-UCB under the "pooling setting" estimator for all arm categories.
Li et al. 2010) where it applies single
Lin- Lin-UCBBCaategory Linear-UCB CChu al. 2011 Li el al. 2010 equipped with calegory-aware embedding (Qi et al., 2022), where the category-awee embedding encode the available arm category information into the arm contexts.
Kernel-UCB represents Kernel-UCB (Valko et al. 2013) under the "pooling setting" where applies single estimator for all arm categories.
KMTL-UCB (Deshmukh et al. 2017) estimates the 'task similarities" with received contextual information, by considering each arm category as a task. The estimations are based on a variant of kernel ridge regression.
Kerne-UCB-Imn is Kernel-UCB (Vakko et al. 2013 under the "disjoint setting" Li et al. 2010
where it learns individual estimators for each arm category.
NCural-UCB stands for Neural-UCB (Zhou al. 2020 with single neural network to evaluate the reward, and calculate the upper confidence bounds with the network gradients.
Neural-UCB--Catggor refers to Neural-UCB (Zhou et al. 2020 with Neural-UCB with category-aware embodding (Qi ct al. 2022 for utilizing the arm category information.
Neural-TS Zhang et al. 2021 utilizes a FC network to estimate the arm reward, along with a
Thompson sampling (Agrawal & Goyal 2013) exploration strategy.
EE-Net (Ban et al. 2022 utilizes two FC networks for exploitation well as exploration respectively, where the gradients of the first network is deemed as the input of the exploration (second) network.
B.2 Three-level Arm Hierarchy
In Subsec. 6.4 we further extend the bi-level HgN-Bandit to three-level hierarchy settings: (1) arm hyper- category level; (2) arm-category level; and (3) arm-level recommendation. Here, for each of the three data sets, we group the existing arm categories into three hyper-categorres using K-means clustering, where the category feature for clustering is determined by averaging the arm contexts associated with that category. [ = 1,000, 1 E [T], and compare with kernelized and neural baselines from Subsec. 6.1
We also let
To extend H-N-Bandit to the three-level hierarchy setting, we introduce an additional hyper-category-lleel model. Similar the original category-level model fc, the syper-category-leve model incorporates an exploitation neural network for hyper-category reward estimation and an exploration network for computing potential gains. Here, hyper-category representation is derived in manner similar to Eq. encoding both the mean arm context information and variance information. In each round, the process consists of: (1) hyper-category filtering, followed by (2) category-level selection (lines 7-9, Algorithm [ and finally (3) arm-level recommendation (lines 11-14, Algorithm [ Since the true hyper-category reward not accessible, the eeper-category-level model is trained on pseudo-labels generated by the category-level networks, similar the training process of the category-level models from Subsec, 4.1
18

---

Published in Transactions on Machine Learning Research (01/2026)
C Complementary Experiments
In this subsection, we present complementary experiments to further analysis H2N-Bandit's 's behaviors and properties.
C.1 Empirical Validation of Effective Dimension Reduction
By definition, we can first let MrK be the kernel Gram matrix formed from all TK arms observed up to round T, and let Mar be the Gram matrix formed from three arms per round (chosen, oracle-best, best-witii-chheen-aatgggrrn caieeriiooooo-oceggrrrrreeeee
After re-indexing, M3r is principal sub-matrix of MrK: hence, by interlacing, (c(M3T) S (M(MTK) for s 3.. For any PSD matrix M with eigenvalues {M)(M)} in non-increasing order and g(u) = log(1 - u/ we have log de + M/A) = =x (M)). Applying this to M3r and Mrx yields log det (T + M /))
E ((s, S Ei=19(((MTKK) I ((=1g(p(MMrx))
log det(I det(I+MMr Mrx/A), A), where the first inequality follows from 14(Mar S (M((MK) (since MyT is a principal sub-matrix) and the monotonicity of g, and the second inequality simply adds the nonnegative tail terms for i > 37'.
Afterwards, using the same denominator log(1 + TK/A) for the normalized effective dimension then gives d(MaT, A) S d(MTk,A) A), with equality only when the omitted arms add no new kernel directions under the kernel feature map.
On the other hand, Fig. empirically validates this behavior on three datasets: the 37 curves are uniformly lower than the TK curves for all T, grow more slowly, and typically saturate earlier. This indicates that adding only three representative arms per round introduces fewer novel directions in the kernel feature space than including all K candidales, thereby reducing the used capacity without harming learning stability.
Effcctive Dimension Growth: TK 3T
Yelp (T-1000, K-20, d-41)
Movielens IT-1000, K-20, (m41)
Amazon IT-1000, K-20, dm413
Nomsitee eheertiee Oimesston
.300
TK aamss
TK ams
TK amm
37 amms
3T ams
ams
220
150
120
1000
200
403
Figure 4: Normalized effective dimension vs. rounds Each subplot compares using all TK arms per round (blue) with three arms per round (3T, orange). The 3T curves are uniformly lower and saturate earlier, corroborating d(Msr, A) I d(Mrk,A).
C.2 Computational Complexity with Different Gradient Input Pooling Scales
To keep the exploration network efficient, we pool the gradients from the category scorer f(] into a lower- dimensional vector before feeding them to (( This gives simple handle, namely the pooling size, to control the imput dimensionality fo without changing the rest of the pipeline. We investigate a wide range of pooling sizes on Yelp and Amazon and report both runtime and regret as ratios to a fixed reference.
Fig. shows that runtime stays generally flat across pooling sizes, while regret remains close to parity with the reference. In practice, this means ((2) is not the main computational bottleneck, and the dominant cost lies the arm-level gradient- based exploration. Pooling therefore offers a safe and convenient way to cap the exploration network's input size and memory footprint, with negligible impact on effectiveness. A moderate pooling size is sufficient to retain useful gradient signal while keeping the system lightweight.
19

---

Published in Transactions on Machine Learning Research (01/2026)
1.1
6.2
Retto t9 reforence (e
Dette to reterente 124 (94)
7.0
Figure 5: Pooling-size sensitivity Yelp and Amazon. Rantime (bars) and regret (line) shown ratios to a fixed reference baseline (pooling size equals to 50). Varying the pooled gradient dimension fed to f(² leaves runtime nearly unchanged and regret near parity, indicating pooling reduces input dimensionality without significant overhead or accuracy loss.
Moviel ens Cumullaiion CENINT oueriap
Amazzon Cumularive CEUNT overiap
Menidars
Anstrr
14000
Cumuiztve COMPE
10090
11000
2000
6000
2000
4000
6000
5000
10000
0
2000
4000
6000
5000
10000
Timerep
Timestep
Cumulative overlsp
Amazon
overlsp
2000
Cumulatve a/t/ overts
Curuusevve oveettp
0000
0000
4000
4000
2000
Tmasrap
Timestep
cumulative count of overlapping categories with the oracle; Bottom: cumulative any-overlap (indicator any match). Both measures increase over time, indicating rising hit rate and coverage in category selection.
Figure 6: Category-level overlap trends. Top:
C.3 Category-level Selection Trends
Next, to assess how well the category stage focuses the arm search over time, we track two complementary signals: (i) the cumulative count of overlaps between the selected categories and the oracle-optimal categories (summing the number of matches at each step), and (ii) the cumulative any-overlap (adding 1 whenever at lcast one selected category matches the oracle at step). Fig. i shows consistent upward trends for both measures on MovieLens and Amazon. The any-overlap curves grow consistently, indicating that the selector routinely includes at least one optimal category as increases. The count curves rise faster than the any-overlap curves, reflecting growing multi-category agrocment with the oracle and thus broader coverage among the top choices. Together, these trends suggest that the category-level model improves its hit rate and coverage over time, providing a reliable, compact filter that guides arm-level exploration.
20

---

Published in Transactions on Machine Learning Research (01/2020)
C.4 Conservative Pseudo-labe labels for Non-selected Classes
HHI
Amnoron
base rours)
bzselin louss
laicledid5 partor-03
libe-0.0C portorew
IstelaD pommn 0.)
Inte-nn1, portinn.2
Iazel:07, pomtin.:..
Iabe: in1,, portion 0.5
2300
Cumulettve www.orteergoo.....oo PogReC
3250
Comubatre
2200
3003
2500
200
1000
2030
0000
Time xtep
xtep
Figure 7: Conservative pseudo-labels on non-selected categories. Baseline (no conservative labels) vs. injecting small labels into random subset of non-selected categories each step (varying label magnitude and sampling portion).
We also evaluate variant that injects conservative pseudo-labels into random subset of non-selected categories at each time step. Concretely, after selecting categories, we sample a proportion of the remaining categories and assign them a small target value (e.g., label = 0.05 or 0.1) in place of the usual pseudo-reward, then update the category model with these targets. This aims to regularize exploration by softly encouraging coverage of unselected categories.
Fig. summarizes the cumulative regret. On Amazon, all tested settings underperform the baseline and the gap widens over time, suggesting that conservative labels potentially dilute informative signals and divert exploration loward randomly chosen categories. On the other hand, for Yelp, conservative labels provide a slight early gain, but converge to the baseline or worse, indicating no substantial benefit.
C.5 Effects of Perturbed Category Representation
We evaluate robustness of the category stage by injecting zero-mean Gaussian noise into the arm contexts before category aggregation, thereby perturbing only the category feature (mean + std) while leaving the arm module and supervision unchanged. Concretely, for each round and category c, we add random noise drawn from (0, T) to the normalized arm contexts and vary the scale a E {0.05, 0.1, 0.2).
2000
3007
Cumulaatvve reghes
1500
2000
1009
3500
2000
0
200C
1030
0002
1000
10000
2030
4000
0002
0002
10000
Time stop
Time step
Figure 8: Robustness to rategooy-ropresentatoo noise: cumulative regret under random Gaussian perturba- tions applied the inputs used for category aggregation, for (0.05, 0.2.
Fig. S shows that our bi-level architecture is generally stable under mild noise, with small gaps at o=0.05. As a increasos, performance can vary, and the sensitivity is dataset dependent: Yelp remains relatively resilient even at o=0.2, whereas Amazon exhibits rise in cumulative regret when injected strong perturbations. These results indicate that robustness to category-level noise can vary across domains and be application-speeifi.
21

---

Published in Transactions on Machine Learning Research (01/2026)
Thus, developing dedicated denoised aggregation mechanisms to handle eategory-injectedd noise is promising future direction of our work, to further strengthen the stability under adversarial settings.
C.6 Augmenting Category Representation with Quantile and Top-k Features
We explore two tail-sensitive enrichment to the category representation.
Quantile Category Feature. To help capture rare but potentially high-value information within a category, we augment the category representation with per-dimension quantile of the arm contexts. Let Xe, = (xI,..,,,,,, C Rd denote the set of normalized arm contexts available for category c at round
addition to the mean and standard deviation vectors, Me,t = J Ein X,, Jet = V E. (x, Mo,e) we compute coordinate-wise q-quantile qe,t E IRd with (0, where (9c.el is the q-quantile of ([x.)) (a The resulting feature is the concatenation 1/ 2,2
norm (IMc,t) ce, qc,el), where norm(.) denotes L2 normalization. Choosing a high quantile (we set g 0.7) helps emphasize the upper tail of each coordinate distribution, making the representation more scnsitive to rare but strong signals.
Top-k Category Feature. We can also augment the representation with pooled statistic over the top- arms according to a simple, permutation-invarian score. Given a scoring function s(-) (we apply coordinate vari- ance), select the indices of the & highest-scoring arms, Is = arg top-k<c[m.]] s(x;), and compute the top-k mean x(() E XG. Concatenating this vector with the basc statistics yiclds ttopk norm (IHc,t: o x x2 This heuristic can highlight information-rich arms that might. be washed out by the global mean, and we set k 5.
%ll
Amazon
base isn toung)
1730
beselite Jourt
1000
mesaid quentio
mearen quentia
mwwaddd hept
1503
mwaseed topic
3230
3003
1000
1000
500
step
Figure 9: Quantile and top-k category features baseline, reported as cumulative regret. We compare the bascline +st) with two augmentations that concatenate either per-dimension high quantile top-k pooled vector.
Fig. 9 compares cumulative regret against the baseline. On Yelp, both enrichments provide small, consistent gains; on Amazon, they slightly underperform the baseline. This suggests tail-aware features help when rare, high-magnitude arms carry actionable signal, but can add variance when tails are noisy. Given the dataset- dependent benefits, we retain our basic mean+sst representation as our default, while view quantile/ /top-k features as optional and data-dependent enhancements that the practitioner can choose based on their specific application scenarios.
D Complementary Explanations for Category Reward Modeling and Definition
We first recall that in Remark ! the computational complexity is O(Ic, + Ke,e)) where C, refers the chosen calegories with the cardinality |č,l = B. In this work, our efficiency improvement comes from the divide-and conuuurr workflow based on the category information, which requires our category reward formulation (Eq. 3. Here, we will need our category reward definition achieve the above time complexity, instead of the (K) complexity in conventional neural bandit algorithms (Zhou al. 2020 Zhang al. 2021). This is to make the category-level model adequately learn the relationship between category
22

---

Published in Transactions on Machine Learning Research (01/2026)
representations and corresponding category rewards. Meanwhile, we would like to mention that it is common to introduce specific formulations in order to leverage the arm category information. For instance, (Hong ett al. 2022) assumes & tree structure with known distribution priors, and (Deshmukh et al. 2017) assumes the reward mapping function is in the Reproducing Kernel Hilbert Space (RKHS) induced by the designated kernel. The eveectiveness of our formulation for leveraging the arm category information is also supported by our experiment results, where we also include several basclines that are capable of leveraging the arm category information (e.g., Linear-UCIB-Category Neura--UCIB-Clegoory KMTL-UCB).
In addition, we would like to provide additional explanations for our formulation of the category reward. Recall that under the stochastic contextual bandit scttings (Zhou et al. 2020 Chu et al.) 2011 Valko et al.) 2013), in each round i, the learner aims to choose one arm Ir E Xr with the maximum reward out of candidates X as its recommendation. Here, our definition of the category reward aims to comply with the learner's objective in each round E [T]. In this case, since the learner only required to choose one arm in round with the maximum reward, the target of the category-level model will naturally be choosing B arm categories C. C Ce, so that these chosen calegories contain the arms with highest rewards among all candidate arms. Therefore, our formulation helps align the category reward definition with our overall objective as well as the target of the arm-level model: recommending one arm with the highest reward out of the filtered candidate arms &y In this case, we formulate the reward of the category as the maximum arm reward it contains. Meanwhile, from the theoretical analysis perspective, our category reward formulation also enables us to bridge the category-level model and the arm-level model. Otherwise, it will be implausible to make our regret analysis pipeline feasible.
On the other hand, if we consider some other formulations, the category reward can fail to comply with our objective and thus fail to capture the arm with the highest reward. For instance, let us alternatively consider the category reward to be the average reward of all the arms in this category. In this case, the category reward can intuitively fail to align with our overall learning objective: choosing one arm with the highost reward in each round. This is because selecting arm categorics with the highest category rewards (e.g,, average arm reward) does not necessarily guarantee the optimal arm is in the chosen categories, which can lead to sub-optimal performances.
As example, suppose we are working the online movic recommendation task, under the stochastic contextual bandil settings (Li et al. 2010 Valko et al., 2013 Zhou et al. 2020). Naturally, our objective is to select one movie I₁ E X₂ with the maximum reward as our recommendation to the target user in each round. Here, suppose the candidate arms X₂ are made up with two kinds of movies: action movies and comedy movies. Suppose the target user generally considers all the action movies to be average-to-gol good (arm rewards in this category: mean=0.6, variance=0.033. For the comedy movies, there are a few pieces that are target. user's favorites, but the target user also dislikes some of the comedy movies, which makes arm rewards in 'comedy' category: mean=0.5, var In this case, if we model the category reward to be the overage reward of all the arms in this category, we will be more likely to choose action movies. This can consequently lead to sub-optimal results, even with powerful arm-level model that can accurately estimate arm rewards. This is because the arms (movies) with the highest rewards, i.e., comedy movie pieces that the target user favorites, are located in the "comedy" category.
As a result, it helps justify our formulation that the goal of the category-level model should be choosing category that contains the arm with maximum reward, based on calegory reward definition (Eq. 3
D.1 Categorical distribution and model performances.
Here, our theoretical analysis, which involves the category-level error and the arm-level error and considers the worst-case scenario. In this case, different category distributions will not impair our theoretical results.
Recall that our objective is to choose the arm with marimum reward in each round. In this case, let us consider Iwo cases: (1) a heavy-tailed category with one highest reward arm, while the other arms are of low rewards; (2) a category of arms with nearly averaged rewards. For case (1), it is obvious that the reward margin between this highest-reward arm and the other sub-optimal arms will be large. Thus, it would be easier for the arm-level model to distinguish this optimal arm for the arm-level recommendation. On the other hand, for case (2), the reward discrepancy among arms within this category will be small, which makes
23

---

Published in Transactions on Machine Learning Research (01/2026)
it harder for the arm-level model to distinguish the best arm within this category. In this case, although the arm-level model may pull sub-optimal arm, the single-round regret will be relatively smaller, because the reward difference between the category-level optimal arm and the chosen arm will be small, due to the nature of arm reward distribution within this category of case (2).
Therefore, there naturally exists a balance between (1) the arm-level reward estimation error and the single- round regret, as well as (2) the arm reward discrepancy within the same category. Meanwhile, as we have discussed, the category-level model naturally aims to choose B arm categories that contain arms with highest rewards for arm-level recommendation. Thus, formulate the category reward the maximum arm reward it contains, to reflect this property. As the category-level and arm-level models will be co-optimized along with more rounds, they will become increasingly more accurate, in terms of both the category selection and arm selection.
We would like to mention that under the stochastic contextual bandit settings, the learner will only receive the arm reward for the chosen arm from the environment. In this case, the true arm category reward will not necessarily be available, no matter what the category reward definition is. Since the arm reward distribution within categories is unknown, this is also the exact reason why we train the category-mode with the pseudo-label (lines 17-19, Algorithm pseudo-code). Therefore, the category reward definition in Eq. 3 can be considered as our way of leveraging the category information. Meanwhile, since we will only receive the reward for the chosen arm in each round, it can be impractical for the learner to gain a comprehensive this case, we utilize our calegory reward definition and the bi-level neural architecture to strike a good balance between model performances and computational costs.
view regarding the category distribution.
D.2 The trade-off between the category-level recommendation and the arm-level recommendation.
There are also natural trade-offs between the category-level recommendation and the arm-level recommenda- tion, in terms of (1) the performance trade-off;; (2) the computational complexity trade-off. And they directly relate to the B value (line 1, Algorithm pseudo-code),, which is the number of categories chosen in each round.
D.2.1 The performance trade-off between category-level recommendation and arm-level recommendation
In Table [
we conduct experiments with different B values, showing setting to high values does not necessarily lead to better performances. Here, although increasing the B values can intuitively increase the possibility of choosing optimal categories, it can impose more burden for the arm-level model, which can lead sub-optimal performances as for Amazon data set in Table | Similarly, setting B to overly small values also load to unsatisfactory performances, bocause it limits the power of the arm-level model. Therefore, practitioners may need to choose B based on their specific scenarios, to balance the computational cost and model performance.
D.2.2 Computational complexity and letegory-level identification trade-off
Recall that for Remark [ our computational complexity is O[[C.) +[(,)) (Kae)), Exee, where C2 refers to the chosen categories with the cardinality [č,] = B. Thus, with more chosen categories (higher B values), it will lead to more candidate arms for arm-level recommendation (Eeec [Xe value), which consequently increases the computational complexity. On the other hand, as in Theorem 5.2 the optimal category is guaranteed to chosen by the category-leve model with a high probability, when we have t > T. Based on the definition of T, we see that I will docrease along with incrcasingly higher B values, which can lead to higher chances of including the optimal arm category for arm-level recommendation.
E
Proof of Cumulative Regret Bound (Proof of Theorem 5.1
Here, we denote Fo(.) = ()+ as well as Fa(-) ffA(+)+ UCB UCB.))UCB(() for the sake of notation simplicity. Recall that the learner is expected to choose one arm DF E X, in each round & (T), in order to minimize the
24

---

Published in Transactions on Machine Learning Research (01/2026)
cumulative pseudo-regret, denoted by
R(T) E
(r rr]
where we have Tr referring to the reward of the chosen arm E Xr, and ri being the reward for the optimal arm, such that E[ri|T] = max ( E.,, h (x()). Under the over-parameterized neural networks settings Allen--Zha et al. 2019 Cao Gu 2019), , we can bound the approximation error of neural networks in terms of the reward mapping functions h h.)). Here, we aim minimize the pscudo-regret for rounds, with Rt, 23 E Xr being the chosen arm and the optimal arm in round E [T], the regret bound R(T)
T
T
T
R(T)
Σ
R
Σ
Ee ri
Σ
ha(a;) ha(wi)
t=1
1=1
Σ
min (na()))(ET) - ha(x)), 13
where R2 is the regret for a single round I, and the last equality is because the expected reward is bounded, Xo,, h(xx) as the 'best possibly
ha(x) E [0, 1], in our problem definition. Then, defining x = arg
chosen" arm conditioned on the first-stage selected categories C, we have
R₂ min min(hs (x ha(a)), 1}
min(ha(2)) - (x())) + (2 1} min(ho(Ve; (v + ha(T;) hx(1)) 1}
category-Ievel
arm-level error
where of is the optimal arm category, Ce is the "chosen optimal' category = arg max cEă, ho(Ve,)- Here, we see that the pseudo regret for each round t [T] can be decomposed into two sub-components, namely the category-level error and the arm-level error.
Next, we first proceed to bound the category-level error with the following steps. For the sake of notation simplicily, for the derivation sleps below, we hide the min-operation min('s 1} by default, which will lead to
min(he(ve; .) - ho(He.)), 1
=holueg,t) - Fo((a.t) + Fo(ua,)) ho(Vens)
S hholuet;)) Fo(ue.)) + Fc(ue..)) ho(we,t)
I (o( Fa +z))) Fo((e,.)) + Fo(Ve,)) FA(2;) + Fa(;;) - ho(va.t)
< (ho()e))))) 1) - Fx(2;)) + +xxxxx) - Fo((e; + Fo(Ua,)) (z;)) + FF((x)) ho(
h)(x;) - Fx [x;)) - Fo((gr)) ) + Fo(Va.)) - =A, + (z, - hc(ve.)))
< (x(x)) (x))) + (x) Fo(ue Fo(Ma.)) -A,(#))
( hz(2:) hh((x)) - ho(v
hx())) (x [(() Folue, .)
-FA FA(x,) hx()))) ha( h (tt)
1,
15
ls
where Fi refer to the imaginary arm-level model trained with optimal arms and their rewards {#t, r r+]re(ry and also have क. arg maxxeU >=U Xx., hx(x) being the best arm within the filtered arm pool ULEū, Ke,t oEC, i.e., the best arm within chosen arm categories. Here, the first inequality is due to the category selection mechanism, and the second inequality is due to the arm pulling mechanism Fa(ã,) < FA(x;), as well as h (xx)) < ha(a)) = hv(,,,)) As we have noticod, there are total of five terms on the RHS that we nood bound one by one. Here, terms I I4 refer to the estimation error of our processed arm-level model and the imaginary arm-level model, which can be bounded by Lemma [. and Corollary respectively. Then,
25

---

Published in Transactions on Machine Learning Research (01/2026)
terms 12, 13 refer to the approximation error of the category-level models, which mcasures how much the calegory-level model output deviates from the pseudo label. These two terms can be bounded by Lemma G.1 and Lemma G.2 respectively. With Lemma I.3 we can bound term 13 being the reward discrepancy between the chosen arm 2; and the optimal arm within the chosen categories Zt.
Afterwards, for arm-level error h ( (mx), it obvious that this error can be upper bounded by term 1s. Therefore, we can apply Lemma 1.3 again obtain the bound. Finally, by assembling all the results, we
will have
T
R(T)=
=
Rr
min(ha(0;) (xre,, 13
t=1
T
min { (((()))) - FF + [2(x)) Fo( + Fo((er)) - FA (2x1)
t=1
+ FA( - (xx)
+2- +2 (
- ha (xt)) 13
Then, substitute these terms with their upper bounds with the above lemmas, we will have
T
R(T) <
(a) min
1) Om 213g(m))233-21331/
O(Sm 1/6 -
+ (a)
1) Omm 1/0 ( 2/3
O(Sm [
+ +a) min m (0ll
1
1] 00m 116 Vlog(m)t2/33 2
+ +0(Sm 1/6 -1
LR
T T2 L2 L m
+ + Tlog( ()) + VTER + O
Vm
m/3
LR
T L Vog m
+0(
Tlogl {)) VTER + O
O0TRR/3mm1////// 1/3 222/ m)
V
1/3
+O 11/12 33 1/
Combining the terms, can further lead to
T
R(T)= <
2n 1m)
x 1} - O(m O(m-1/6 Vlog(m)t
1/6
2/33 -2/3 L/)
(=1
+ +0(5m=1/00logmm)
+ (a) -xmmmmm(ll(0:00000000 .)., 1) 10m -1/6 ( 22/
+ +0 /10
+ Tlog( +2 O T
T2 12 /log m
O(TR4/3 m -1/3 122//oo m)
Vm
1/3
133 Vlog m)
26

---

Published in Transactions on Machine Learning Research (01/2026)
Afterwards, by applying Lemma J.9
Lemma J.10 and Lemma J.2 it leads to
R(T) 0
Tdlog(1 (T + +TK/A) (aV dlog(1 + TK/A) - 2log(6) 22
( Tlog( 5) + (TRR + +0 LR T2 L2
Vlg m
O(TR m m/3// L? 2/11'2/Vloomm Vlogm
vm
1/3
+ O(TECR 1/122 Vlog
+ -0Ssm 1/6 /l/gmm)22/66 1 + O( 1/6 /10g())77
<olv Tálog(1+ +TKAA) TTloo((+TT/A)) (av @log(1+ - 2 log(()) + x1/35) + O(1 Mily/logg' (logl))) + VTn))+ (1En)+000 +0(1)
where the last. inequality is because we have sufficiently large network width m, as mentioned in Theorem 5.1
which completes the proof.
F Guarantee for Choosing the Optimal Arm Category (Proof of theorem 5.2)
As mentioned in the main body, for the sake of theoretical analysis in this section, suppose the candidate arms Xg in each round & E [7] are randomly sampled from the context distribution D. Meanwhile, to derive the performance guarantee for the category-level model in each round, we consider the preference scores to satisfy the definition of the Ç-margin among arm categorics. Here, we note that this definition is necessary for defining the 'optimal arm category' and deriving the performance guarantee for the category-level recommendation. Otherwise, consider a scenario where we receive |C,| = 10 categories all with the same category reward. In this case, there will be no need to perform category-level recommendation since choosing arbitrary categories can lead to the highest category reward.
Recall that in each round, we will choose C.l = B categories for the first-stage recommendation. With the definition the category margin, if the optimal calegory falls into the chosen ones, i.e., of E C, the discrimination power of the category-level model must be enough. If the category-level can definitely discriminate the optimal category ot E C,, we can consider that for all the other arm categories, we need to make sure there is no overlap in terms of the confidence bounds with the optimal category. With a minimum category reward interval Ç, denoting error(c) to be the estimation error in terms of category c's reward, we will have
error((c)) + error(ca) 55 - E B((tho(ecs))) - FolMe;a)) ((hc(ee,)) Fo( sC
Ex
E (#)) - Fo((eq()) + (ha(#;) - Fo(Ma,e)) sc
E (ha(w;)) +c( - Fo(va.))) S
(alat)-Foluu haa()))))) -Fo(Ven))
<C
By only considering the relationship between the chosen category and the optimal category, while omilting the expectation E[-] notation for simplicity, can satisfy the condition above by enabling
2 [a(xa]) - Fi + [xt)) - Fo(ve2+) + (āt) h (ax)) [ Fx())) + (FA(at) Fo(var))
- 2 h((z;)= - Fi;;) + - Fc) + [ā;));; - h + ( FA + FA(x)) - Foo(aa))
h((z)) - Fi(x;) + Fx(())) - Fo(u + (,; - (x,,) + FA(,)) Folvar))
hn(xz)) Fo((e,))) + ( - (V
Furthermore, with B = [6,1 tasks chosen in round as well as the notation from Section for G E غ, and can further relax our objective, because as long as our overall estimation error is smaller than B Ç, we
27

---

Published in Transactions on Machine Learning Research (01/2026)
will be able to include of to C.. This consequently leads to
E
[h((;)) FFA(z))) + (x - Fe(ue).)) + Fe(Uen)) Fa(az)) + [F((x)) ha(xa)) + (ha((rs) - hu (
S 5.
where there are a total of five terms on the LHS that we need to bound one by one. Here, terms Z,, 14 refer to the estimation error our processed arm-level model and the imaginary arm-level model, which can be bounded by Lemma [.1 and Corollary 1.2 respectively. Then, terms 12, J3 refer to the approximation error of the category-level models, which measures how much the category-level model output deviates from the pscudo label. These two terms be bounded by Corollary G.3, Corollary G.4 respectively, With Lemma L.3 can bound term Is being the reward discrepancy between the chosen arm æ; and the optimal arm within the chosen categories ã, Afterwards, apply the upper bound for these terms, we will have
B. (x) min{llg(2;; 1 1 E + 7+(()))
1}
+0SSm 1/6 Vlog(m))* 1// 1 2 + -0m Vlogmm//ol 2//3 L2))
1/6
+ log( log(3)) + $V {R 0
tLR tR L2 Mogm
Vm
m/3
+ +0U11113 11. 1/3 L Vlog m) + 113 11/112 L3 1-11/11/1//11111 Vlogm)
2 (7)) min(llg( ( 1/ ز 1) + + min min (11g(1) (7) 12 1}
1/6 2/ O(m 1/6 / 2 +0mSm 1/6 Vlog(m)) 1/ 1/1
0 7 logt ()) +V1
fR + 0
I.R IR Mogmm
mm
m/3
+ 1 m 1/3 Vlog m) + (3 11/12
1/12 L3 1//12////oo/1 llgmm.
Then, for the min(1lg(2;; (A)l-1))/ " 1}, min
mi D)-,, 1} terms, since we have the candidate arms X, drawn in an i.dd. manner, we can follow an analogous approach as in the proof of Corollary G.3 By constructing the martingale difference sequence and applying the bauma-Hoeffding inequality, we will have
1
E min (lo: E 1}]
E [md 1)}
rE((]
E [min((l((:;((0)))>)) د 1}}
rE((]
Σ E [[nin((o(de::(0)))))) x, 1}] O(m 1/6 11/61/6 xlog(m){2/3x221 )
reld]
min(lgde::/00>>>))) | 1} 13|+00 01++011 (og( + 1m000mmmmp))) 1/6 Vlo(m))22/33 2/3 -2/31,7 1,3)
rEed
< 10V log(1 (K/A) + ( ( + mm-00mmmm01 1/6 213 -2/3
where the first incquality is because of Corollary 7.7.4. (a) from Meyer 2000 sccond incquality is bocause
of Lemma H.4 and the last inequality based on Lemma J.9. Lemma 10 and Lemma J.2) Similar bound can also be obtained for term min[llg( [0te:=:))))))///) /m/ll//mll (=))))) 1).
28

---

Published in Transactions on Machine Learning Research (01/2026)
Finally, by assembling all the results above, we can have
B. B. 0 (V
d log(1 +K/AA) (ay dlog(1+1K/A)) (aAAA)-22og/// log(0) + +1/22)
+0(Sm (lolmm///oolmmmlll 1 1//7,
+ Om 1/6, (log(m) 22/3 1.3
5nt { + +0( Log( g)) V
tLR Vlogmm
+ 0
+
Vm
m/33
+ O
1/3 1/3 L2 VVogm) + 1 L3 Vlogm).
Then, with sufficiently large network width m indicated in Theorem 5.1 can finally have
t dlog(1 + tK/A) (ay dlog(1 + tK/A) 2log(ö) + 11235) + Oly VER) 0(1) 2
B.5
G Bounding Estimation Error for the Category-level Model
Recall that the category-level models fC .Se are trained with the output of the arm-level model fA. As shown in the main body, this will lead to the error term min((Fo(M...) - FA (x,)). 1}. which bound the output difference between the category-level model and the arm-level model. In order to derive the T'round regret R(T), after accumulating this error term for rounds, we need to bound the following two terms
Σ E min (F(eeF - -A((x)) 1} (E[T]
Σ E [in((F - Fo(Meg 1 X EE(T]
where we recall =c( (v 10 16 (V (Va.); 0 1-11 represents the estimated score for the chosen category Ct, while on the other hand, we have Fa(x;) = fA (æạ Al]--1 + UCB,( being the score from the arm-level model. Here, the first objective measures the approximation error of the category-level model Fc, which the second term measures the error of the imaginary category-level model that has been trained on optimal arm categories. Then, will proceed to introduce the following results.
Lemma G.1. Given past collected records, we suppose nI. J salisfy the conditions in Theorem 5.1 and randomly drow the porameter [0 10 P.- {Me.,r For.r bre(t-1] up to round t generated by a policy. Then, with En >> 0 and the probability at least 1 6, given pair of arm category and its pseudo reward Fo we have
|r]rE((-11- Consider the past records ([@0) (2
Σ E rE(t]
min (15e
(Ve,.
10 f0 (VIC (Ve (Ve..)) ( (0))))) I--1) - 13 X
s 0 (lgg + VIER + O
LLR
PRA//3 L2 L///3LLVogg A.Vloggm mogm
+
Vm
m-/3
where Fer.r is the pseudo reward generated by the arm-level model FA(-), as defined in Algorithm 1
Proof. We prove this Lemma following a similar approach as in Lemma C.1 from (Ban et al. 2022 for the LHS, we have
First,
(ve 1-1) 12) (V (Va,t): @ (111) -F.t < |1500 (Va.i ( + ( (1) (Va..); 10 ) |Fal S 0(1)
based the conclusion from Lemma H.1 well as the value range for pscudo reward F. Then, we define the following martingale difference sequence with regard to the previous records up to round E [1]
V- = B( (
10 1-))) + (V (1) (Vc.. 10 (0)))) - -Fa.rl
-15 (V...r:(6 (0 (-)) (2) (V. (vc.:); 10 10 - Fer.T/
29

---

Published in Transactions on Machine Learning Research (01/2026)
Since the records in set P, are sharing the same reward mapping function, we have the expectation
[[] E [ Uar.ii el ( 18 (VSC (Mor, ( -
-E(L6 (vo.ril0
21) 1-1) fe (VS6 (Verr)) (-1)) Fer.r [| = 0.
(
where Fr denotes the filtration given the past records. Then, we can have the mean value of V, across different time steps being
1 Σ V
-
Σ rE(r]
E f (ve, 100
10 (V (Ve,. 1 I-1) Fe,
t rE
Σ rE|d]
(v. fc
( ) 1r-)) -Fe..l
with the expectation of zero. Then, we proceed to bound the expected estimation error of the exploitation model with the estimation error from existing samples. Afterwards, by applying the Azuma- Hoama-Hoefdding inequality, with a constant 8' E (0, 1), we have
P
E
.r 10 10 18 (VS (v.,r) 16 -Ferrrl
FE|O]
1 Σ TE(T
(v 1- _ ( 01) (o,, ); 0 - -Fe.rl 2 2(1)
2 1 v log {)
S
( |. 1 2) As we have the parameter O ( 10 || c
J bre(d), with the probability at least 1 - 6, the
expected loss on 10 ()) could be bounded as
1
B (1) ( 10 (V)
(V (0 I--)) Fcr
i 7E((]
( (Ve.. (v...i 10 (
2 10 l-=1) +e..1+0(11) / log(
1
rE(
where for the second term on the RHS, we have
1
Σ
(Versri 1 I- + (V (Vo, ): 10 Font
7
TE(
110) (v ( 5 (2) (V.6)) (Vo, 100 )--1) )--)) Fc,
FE(T]
tLR²
tR 1 Vlogmo
+ 00(1
+ +0
Vm
1/3
ER + O
LLR
tRA/3
L'v
S
vm
m/33
where with the notation in Lemin H.7 and Lemma H.6 and we ca further have the definition for the first
term being & inf (ecB( Rm ErEt | (Ve..: ! + (V(()
(Me..r); 2 (V
Fe..r []] 0,
with [Oc]o be the initial parameters from either of the two category-leve networks. Here, the inequality is the application of Lemma H.7 Summing up all the components would complete the proof.
Mcanwhile, apart from the sequence of chosen categories (Vo,. he(T) we can also have comparable results for other sequences of categories. Next, we will introduce the lemma in terms of the optimal categorics in order to prove the bound for our second objective.
30

---

Published in Transactions on Machine Learning Research (01/2026)
Lemma G.2. Given past collected records, suppose and randomly draw the parameter 102 Je, (0 { ( I-,
nc. m.nc,
satisfy the conditions in Theorem 5.1 1-rettt---]-- (
Consider the past records Pe (Vet.rr (e..://..) up round are generated by a policy. Then, with probability at least 8, given pair of arm category and its pseudo reward (Ver,s we have
Σ rE(t]
E min (I5e (V 10: Sc
(VIC 1 (ue (u. 100 - -F 13 Xr
50( ooytoooo tlogí .)) + tEN + O0
LLR 1 P 1.2 V.og. Vlogm vm
+
m\/3
+ O 11/3 Vlog log m) + OttEc m 1/12 L3 Vlog m)
where Foz.r is the pseudo reward generated by the imaginary arm-level model FA("), which is trained by optimal arms ( reeeE(--
Proof. The proof of this lemma follows an analogous approach as in Lemma G.1 Recall that our processed category networks fC (s (0 (s [ are trained by the records related to the chosen arms and their rewards {T Frems. Here, we first consider the alternative imaginary category-level models (1),)) DD,, and arm-level model (1(:: These imaginary models are trained by the records optimal arms as well as optimal arm categories.
fc (1),* (+: (DDD f(() (+: (
Similar to Lemmna G.1 based on Lemina H.1 we have the LHS of the objective bounded by O(1) Then, we define the following martingale difference sequence with regard to the previous records up to round E [t] in terms of the optimal arms and categories, such that
Vi = E[ (Meriri 100 (2) Ir-1) + 10 (V
(1)) (Vor )i (2) h--1) h--)) Poy |] (1),
-I,(l)) (ve.ril0 (1),
(1) b--)) + (!)) (V (Ver.): |0 -+==))++)~----)) -Fc.
where we also have its expectation w.r.t. the filtration Fú E[V F+] = 0. Next, by applying the Azume- Hoeffing inequality, with 1 > 8 > 0, we can also have
P
E
0 (1) (-))))
1 (VI (ve, ): 10 106)))1-)) 1)- - Pct.r]
rE(T]
2 V log( ()) s
Σ
(Ver 100 + 10 (2) ( (Ve, 10 1--1) Pog.r 2 0())
(1)
rE(d
After applying Lemma H.6 and Lemma H.7 we will end up with
Σ
(Meg.r:
10
U1 (-1) +
10 (VS
(v (v
2) 11-1)))))) -
t
TE]A]
1
Σ
((l) (vez.ri
(1), 1
C I--1) f( (V/6 (1)+ (Meg, ): 1 (2),2 ))))))))))))
(2-1) -Po..7 2
Vt
rE|O]
LLK
TR4/3 V2oooomm m
+ +01
O
Vm
1/3
En + +(1)+ + $ /V
ILR² TR1/3
Vlog
+ +0(
vm
m!/
where the last inequality because the parameter sphere B([Oloo Rm-1/4) also includes the imaginary model parameters. Noticing that the current bound is built upon the imaginary category-modehs we then need to further extend this bound to our processed category-level models.
31

---

Published in Transactions on Machine Learning Research (01/2026)
With Lemma H.6 we know that the processed parameters
10 as well as the imaginary ones
both fall into O Rm Rm-1/4), As result, can have
|50 (V (Ver.t O (1-1) + fo (vic (Ve,,))(
1--1)
2 h--1) (h-1)
fo (Vez 1 [ -- + (e,,)
$ |se (ve (Ver.ii O |-- (ue,ri [-11]
+ +15e (V (ucg,>);
(-11) ( (Vez ); 10
S Oftm (/ARmm- + 0 1/3 222 logm)
+ + | (V (ve, . ): [ "T--) - f1 (V (Vez ): |-
where the incquality is by applying Lemma H.3 Then, for the last term on the RHS, supposing the input gradients are normalized by a coefficient [mL]
we will have
1 1e (VSC (Uez 0:10 ? ---)) -
Ue (u (0)
15e (2) (VSC ( (Me 2 1--1) - (VI (v:))
+ +150 (V (vc,, 1 - fo (v (
< 0 -1/1-//// VL) + 0 m 1/3 1/3 mlgmm
+ +150 (VIC ( 0 C (--1) - 10 (V.6 (1) (V 1: r 1-)
< 0 1/4//) + /3 1/3 L2 Vlogm) + O /3mm 1//2 2 m)
where the first inequality is by the triangular inequality, the second inequality is because of Lemma H.3 and the final inequality is because of the fact that over-paramettrriee FC networks are Lipshitz continuous w.r.t.
some constant & > 0 (Allen-Zhu et al. 2019) as well as Lemma H.4
In addition, apart from the performance guarantee for the T rounds altogether, we can further have the performance guarantee in terms of each & E [T] round, if each candidate arm is drawn from a distribution in an i.i.d. manner. This can be done by extending the conclusion well as the proof workflow from Lemma G.1 and Lemma G.2
Corollary G.3. Given past collected records, we suppose m, MC, satisfy the conditions in Theorem 5.1 and randomly draw the parameter ( (0
(2) ~ (,, brree(t--]- Consider the arms within candidate arm pools {Xrirejt) are drawn from a distribution D in the i.i.d. manner, and the past records Pt. = Fe, up to round are genertted by a policy. Then, with probability at least - 5, given a pair of arm category and its pseudo reward (Verss Forth, we have
E min (15@)
(veni ( (0 (V1 (V (Va.): I1-1) - 11-1)- Forcch 1} Xg
1--))
s <oly (ort)) + V
ER 0 Vm
LLR
L2 m
m/33
where Foct is the pseudo reward generated by the arm-level model FA(.), as defined in Algorithm
1
Proof. The proof of this corollary follows a comparable approach as in Lemma G.I. Similarly, based on the conclusion from Lemma H.1 and the value range for pseudo reward 7, we define the following martingale difference sequence with regard the previous records up to round 7 E [t]. as
V- = [[Se (Vl 19 + (V.6))
(1) (v :): 10 (2) -
-Is (Vo.ril0 C 1- + ( (V.C () (r-)) -
(1)
Since the records in set. P, are sharing the same reward mapping function, we have the expectation
EVV[FF]] F+] = (1 (Me..i e0 (1) ) + 16) (v (ve, ( -Fer.rl
-E(1S0) (U 1- + f (V ( (Ve,:): (0 (-1)) Fer. = 0.
32

---

Published in Transactions on Machine Learning Research (01/2026)
where Fr denotes the filtration given the past records. Then, we can have the mean value of V, across different time steps being
1
1 V+ = t Σ t rEld]
Σ
B fl 100
( (Ve,, (0 10 I--1) - -Fe,iel
reld]
- +
Σ
1 (v,,, rE(d
16 (VIC :) 10 -Fa,
with the expectation of zero. Then, we proceed to bound the expected estimation error of the exploitation model with the estimation error from existing samples. Afterwards, by applying the Azuma-Hoefdding inequality, with the probability at least 1 1- 8, the expected loss on [ could be bounded
1 Σ
B
11)
10 (V Ver. ) (r))))))
(--1) Fer.ill
7 re(d]
Σ rE(d
Won.r (o..n: + (V U ): ( - -oorr + V log
where for the second term on the RHS, since we have X, ~ D,r E [t] as well as [ 1 h. e 2
( Ir. ( Ir it will lead to
Exeny 15 (Vent (
01 1111) + (V (ve,))) 10 ( ((-1) Fand
1
Σ
1/0 (Ven.ri 0 0 h- + 1() (VI (1)
(v..:)) : (00 Fenorl
t
rE(e]
1
1 (Van.i 4 1--1) + 10 (V (1) (M 1:0 I--1) -Feri
vi
rE(d]
tLR
tRA/3 L22 LLVlogmm m
+ +111 +
+ O
Vm
1/3
ER $ V 0(1) + Vm
ILR
V.2/logm
O
m/3
where with the notation from Lemma H.7 and Lemma H.6 regression difficulty being { inf
will also have the first term measuring the
eeeB km--)) 1 Eregq |.e (() (V (Mo, 0
Te,,> [] with [Oc]a be the initial parameters from either of the two category-level networks. The inequality is the application of Lemma H.7
Summing up all the components would complete the proof.
Corollary G.4. Given past collected records, we suppose m. VlC, J salisfy the conditions in Theorem 5.1 and randomly draw the parameter [00)e. Jc, (00 @ 1, (2)) Tre(t---- Consider the arms within candidate arm pools (Xrbrejt are drawn from distribution D in the i.í.d. manner, and the past records up to round are generaled by a policy. Then, with probubilily at least 1 5, given
'P = Tee. pair of arm category and its pscudo reward VerdTTaat we have
E
min
(10
(ueg ( (1
(2)) (V.C
(1) (M 10 1--1) Poy.l, 13 2i
0 I logl x)) + / ER 00--1
tLR
tR4/3 L2vlo m
+ ORH4/3 m1/33 2 llgmm
Vm
m//3
133 1m
/lg m)
where Fo.. is the pseudo reward generated by the imaginary arm-level model Fx(,,, which is trained by optimal arms (xt,, rre(g-
33

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. The proof of this corollary follows an analogous approach as in Lemma G.2 and Corollary Similarly, we first consider the alternative imaginary category-level models SC f()* (:
G.3
D.Sc
(: f
1 c "D,
and arm-level model fä(: [0x]). These imaginary models are trained by the records optimal arms as well
optimal arm categories. Analogous to Lemma G.1 based on Lemma H.1 we have the LHS of the objective
bounded by ((1). Then, we define the following martingale difference sequence with regard to the previous
records up to round T E [t] in terms of the optimal arms and categories, such that
V =[] (Ve..r: (0())))))))))) (1--1) + fc (v.f. (e..));(e "h- -Fa.1l
-Is(! "Vor,, ( (1) I--)
f() (vSe (Verr): 100
Pop.1l-
C
where we also have its expectation w.r.t. the filtration F7, B F+] = 0. Next, by applying the Azume- Hoeffing inequality, with 1 >> 6 > 0, we can also have
(e..ri ( (--) + ,()) - (Ve..): ()) b---) - Top.7
P
rE(d]
2 V7 (ost S 6.
Σ
|e (Ma, ri 1: 100 + 10 (2) (V
(1), (Ve, ); 10 10 - -,,,,| 2 0(1)
TElO
After applying Lemma H.6 and Temma H.7 we will end up with
((()))(( (Mez 1:1
C 11-1) + 18 fV (Vez ): 10
? 1--1) - -
7 Σ
10 (Vot 1 (1 )-1) + (! (VI6 10) (Veg.)): 10 (--1) Fcc.rl
()),
=E({]
| (v (ug 10 (1) 1--1) + 1 (2)* (V (1), (Uzz.)) ): 10 (--)))))> - -P
VL
rE|A]
+0(1)+ + tLR
1R L2 Vlog m
+
Vm
m
{ 1 + +011+
LL
tRA/3 L² Vlogm 1/3
0 m
where the last inequality because the parameter sphere B( Rm-1/1) also includes the imaginary model parameters. Noticing that the current bound is built upon the imaginary category- models, we then need to further extend this bound to our processed category-level models.
With Lemma H.6 we know that the processed paramcters ( @00 1-1 as well as the imaginary ones both fall into OCOO.. Ron -1/4) As a result,
|
10
(1) 1--1) + f (V (ver
C
(Met.ri 1
(Me,, ): e |--1)
150 ( (uerri
16 (U
+150 (V.e (M
|--1)
f (VIC ( . ); (--))))))
< 50(Rm 1/4 VL) + /3 m 1/3 L2 /lgmm
+ +150 (2) (V (Ueg.): ) 1 1-1)
(2) (ViC (1)
(Ve:.)) ): 0 |-
34

---

Published in Transactions on Machine Learning Research (01/2026)
where the inequality is by applying Lemma gradients are normalized by coefficient [mmL)
H.3 Then, for the last term the RHS, supposing the input
will have
1 (V.C (1) (Me,
(2) ---) (V (Ve
1 (2) (VIC (1) (uc,
(2 (VSC (
0 1-1))
+ +15e (VSE
21 1-1) (2) (V (M 10 0 h-
S 50(Rm 1/4 VL) + O m V llggm
+ +15e (2) (Vfc (Vzz --1 10
11) Sc (uet ); 10 --
< S0(mmm + 0(1 1/3 /lgmmm + OEtc R2 1/12 log m)
where the first inequality is by the triangular inequality, the second inequality is because of Lemma 13 and the final inequality is because of the fact that over-parameterized FC networks are Lipshitz continuous w.r.t.
some constant &c 0 (Allen-Zhu et al. 2019 as well Lemma H.4
H Lemmas For Category-level Neural Networks
Here, without the loss generality, we use fc to denote both fe and f0 since these two models will follow very similar patterns. To begin with, given the input feature vector E Rd, we denote the L-layer fully-connected (FC) neural network with network width m by
fc - CI D.O,) æ2
(8)
1=1
where with & being the ReLU activation, we define the intermediate hidden representations h1 l E (o...., as
L-13
he = x, h4 ((Oth-i)), [I.
and we also have the binary diagonal matrix functioning as the ReLU activation being
Dj = where I((-) is the indicator function. Afterwards, the corresponding gradients will naturally become
[L-1].
Verfc(z; = 1h1-102 E hh h
(9)
Recall that for the category-level models, for E [L - 1), each entry of O drawn from the Gaussian distribution (00.2/m) Each entry of O2 is drawn from the Gaussian distribution NO0, 1/m).
Lemma H.1. Suppose m, 122 satisfy the conditions in Theorem 5.1 Based on the Gaussian initialization
of weight matrices, with probability at least - O(TkL) - 22 2/3 L)) over the random initialization,
for all E [T), [k], satisfying || Ool1 & with S OI. 992 log m]] -3), holds uniformly that
l 2) 0(1).
VVoSc 0]]l s O(VT). [VoC
where (.(0) = (fo(#;; @) - 222 is the Ta prediction loss in terms of the arm æt-
35

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. (1) is simply application of Cauchy-Schwarz Schwarz inequality.
I-1
1-1
[So(æ; θ) = | II
D.Or) s | II
D,O:) Me,ll2 s 0(1)
[=1
1=1
where the inequality is based on the Lemma B.2 (Cao & Gu Mealll2 = 1. For (2), holds uniformly that
2019 and the fact that 1r I O(1,, and
[Vofc(ve,; O)ll = S) vect Vel S O(VT.)
where fll I O(L) is an application of Lemma B.3 (Cao & Gu For (3), have ( [4,1 VV.c(u... 0)1 O(VL).
2019) by removing vm.
Lemma H.2. Suppose m, nc, d2 satisfy the conditions in Theorem 5.
With probability at least
O(TLL) (opp0-((mm2//11)m L)), for all [T] [K], 6 O satisfying
1 @ull2, ||@' Gollz I with
S (LL-0/21000 m] m)]+),, il holds uniformly that
[so( θ fa(1; Ø') Sola O θ 0') Oww2/313 log m) mmmmm>l|))) O'|2
Proof.
Based on Lemma 4.1 Cao & Gu 2019 it holds uniformly that
Imffo( +) vmfc(z; O') www. (a: O²), - S /33 m log(m)) -01l2.
where vm comes from the different scaling of neural network structure. Removing Vm completes the proof.
Lemma H.3. Suppose m, nC, m. T2 satisfy the conditions in Theorem 5. OTTLL) exp( - 2/3 L)), for all t E [T]. [k], O e' satisfying w < (L--
With probability at least
Qull2, ||@' 0 S with
-// (/ol m)- it holds uniformly that
[)((;; - so((: θ') <O(wVL) 0( + Vlog
(10)
Proof. Based on the LHS of the inequality in Lemma
H.3 we have
[f((; o) fc(::
() e') + / logm) 0l
Ver | @'|1 2/3 logm)) -
10 2
log m)
e - 0'1
The proof is completed.
Suppose m, nC, 92 satisfy the conditions Theorem 5.1 With probability least O(TkL) exp( 2/3 L)), for all [T] e [k], O, O' satisfying
Lemma H.4 (Theorem in Allen-Zhu et al. 2019
| Ool12, ||@' Ooll2 S w with OLL 9/2 m] 32 il holds uniformly that
Vefc(z; 0) Vefo(æ;; 0')l So(w>/3 (e
(11)
Lemma H.5. Let (,( (fc(z,; 9) r2) being the La prediction loss in terms of the T,. Suppose m, n1, T2 satisfy the conditions in Theorem 5.1 With probability at least O(TkL²) expl 2xp
over randomness of 11, for all E [T], and @ O' satisfying | Opllz S w and @ 1pllz S with
w < [l. -3/2), it holds uniformly that
L, 2 (.( + (VoL( - -) -
where (oggm))))))))).
36

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. Let L be the derivative of L, with respective to fa @). Then, it holds that |4/ - O(1) based
Lemma H.1
Then, by convexity of Lt, we have
-
" 0') - (o( 0)]
2 ( O' A - -
[fc(a;;;") - - fc(m; () (Vic (m;; 0' "' O)
2(VeL. 0 - Q - -P-il [5c(;; 00) fc(m;; Q - (Vic(z;; ① @' -)
(9 2 OV 0' Q) -ww4//3 3 logm))
L, @' ))
where (a) is due to the convexity of L. (b) is an application of triangle inequality, and (c) is the application of Lemma H.2 The proof is completed.
Lemma H.6. Suppose m, Mcs 92 satisfy the conditions in Theorem 5. With probability at least O(TkI?))xp) expl (/mm//33 L)] over randommess of Oo for any 0, holds uniformly that
|10 Doll2 s O(R/m² /), e [T]
Proof. Let S O(R/m2/4). The proof follows simple induction. Obviously, On is in the sphere B(O w), where the center is O and radius is w. Suppose that θ O Or E B(O) w). We have, for any t E [T],
T
T
| - 00l2 S
1 0,11l =
|LLL & Σ nVL
t=1
t=
OTR VL/ O(R/m!14)
The proof is complete.
Lemma H.7 (Theorem 2 in Ban et al. 2022)). ). Let L(( = (fc( : Q) - -21)2/2. Suppose m, nc: 122 satisfy
the conditions Theorem 5.1 With probabilily al least - O(ThI²) expl- -S(mm2/33 over randomness of O given any R holds that
T E.)O))) & [c((0')+00)
T
TLR
TRA/3 1,2 (raA/s,2/oog' m
vm + 0
(12)
1/3
where θ" arginfeen Σ C()).
Proof. Let O' E O R). In round 1, based on Lemina H.6 for any E [T), ||0, - -0'122 s sww. (O(R/m21))
Then, based on H.5 it holds uniformly
L.(O,) (()))) (VV()))))) +e,
where e = 1234/333 L3/ogm) m).
Therefore, for all E [T], O' E B(O,, R), it holds uniformly
(.)))) - (.)) (o) (e; 1 O O¹)
(b) O O
0 1
10
O'|
2m
|
1 1/|
O(Ta)
27
37

---

Published in Transactions on Machine Learning Research (01/2026)
where (a) is because of the definition of gradient descent, (6) is due to the fact 2(A,
||A||| + ||
|| B| p. (c) is by 10 + 11 = (o. O()
Then, for 7 rounds, we have
Σ
T
(O.)
Σ ((')
T
(1)
Σ t=2
1
Ln Te
2n
27j
27
t=1
t=1
1
Σ
Lm TT
2m
t=l
R2
<0(
Σ La + Te
mmn
(2)
TLR
TRA/3 VlgVooggn m
(1) +
+ O
Vm
m 1/3
_²2 where (1) is by simply discarding the last term and (2) is by 1) Vm
and replacing e with w = (RR/m/))))
0
Bounding Errors for the Arm-level Model
In this section, we would like to prove the bound for arm-level recommendations. Recall that after filtering the arm categories C2 with the first-level, namely the category-level, recommendation, the arm-level model intends to recommend one arm H, E U.ed. Xe, accordingly, where Xe, refers the collection of arms for
each category c C G. First, we would like to restate the definition of the NTK Gram matrix as well as the effective dimension again for readers' reference.
Definition 4 (NTK Matrix (Jacot et al. 2018: Zhou al. 2020 ). Let. N denote the Gaussian distribution. With, define
y
M = Vi = (a,, (z))
No
ypl
vp
3,1
3.j
V 1. 2E 2B 1 (b(a((())
M = 2M W,
+ w...
Then, given the chosen arms {x,) and the optimal arms { the Neural Tangent Kernel Gram Matris is defined accordingly as M (M- + x2//22 3T
Meanwhile, similar to existing neural bandit works Zhou et al. 2020 Zhang et al. 2021 we have the effective dimension definition regarding the NTK Gram matrix
Definition (Effective Dimension (Zhou et al.) 2020)). Given the chosen arms {xt) and the optimal arms {x; 17-1 over the finite horizon T, the effective dimension d is defined as
J log M/AA)
log(1 +KK/A)
which measures the vanishing speed of eigenvalues of Gram matrix M.
The effective dimension here essentially measures the vanishing speed of the Gram matrix cigenvalues.
Apart from the NTK defined above, we also define the gradient mapping w.r.t. the neural network parameters as following, where the gradient-based mapping will be close to the NTK-based mapping under the over- parameterized settings. By applying the Lemma J. the arm-level model, when it satisfies the conditions in Theorem 5.1 we have the expected reward of an arm x E X, being
E E[r[c] (a()) = (g(2; O A))), é [0
38

---

Published in Transactions on Machine Learning Research (01/2026)
where there exist parameters @ such that ||0 [@aloll SS/mm, >> 0. Meanwhile, we also denote the following NTK regression parameters
- = +
Σ
g (A1o)) g(x,; (O))o)/m
FE[t-1|
(0)
Σ
g
(O100) rr vr/Vm,
rE(t-1]
E1-1 = A
g (0 (0
rE(r-I]
b
E
g( A|)-)) T/ r
7E(t-11
where (r.,,r),7 T [t] respectively stands for the chosen arms as well their rewards, and g(æ; θa) R refer to the vectorized network gradients w.r.t. O A when taking the input. Then, with the above definitions, we proceed to bound the recommendation error of the arm-level model.
1.1 Regret Bound for Arm-level Recommendation
Next, would like to bound the arm-level recommendation error, which refers to FA(Z;) - hc( This measures the difference between the arm-level model output and the arm category reward (i.e., the reward of the optimal arm in the filtered arm categorics z7). Here, the estimation error of the arm-level recommendation, can be transformed to
min (Fa(#z) hac 1)
(ar.) hx(w))) ho(ver)) 1}
$ [F(())) hA (2x)) + (11
ho (vc,,))
FA(x:) - hA (xx1)
+ h(l(), - (ā;)))
Error for Reward Estimation
Reward Gap
where recall that के- arg max w = xe..) [ refers to the optimal arm within the filtered candidate
cEC,
arm pool. Here, the first term on the RHS refers to the estimation error of the arm-level model for the reward of chosen arm Lt, while the second lerm refers to the reward gap between the chosen arm æ, and the optimal arm in the filtered candidate pool T
1.1.1 Term 1: Error for Reward Estimation
Here, we will have the following lemma for bounding the first term
Lemma I.1. Suppose the arm-level neural network fa(: (0ale-1) has been trained on chosen arms and their rewards (wr,vr)re((-1) with J-ileration GD and learning rale n) Meanwohile, fa(: (AJe-) is L-luyer FC network with width m. Suppose have J.n satisfying the conditions in Theorem 5.1 Then, with the probability at least 1 - 5, we will have
[F(())) hx())) (7-1(a) (g (0ll-1) xT O(m 1/6 /log(m)e/33 22/
+0Sm 1/6 log(m)) 1/6 ( 1/ -1/6
By definition in Lemma I.4 and Theorem we have FA FA(x f (z AAll-1) UCBa( and the upper
confidence bound UCB, (x)) (a)) v (2;; | E, 1 ()tt-1)) where
Σ, = AI + Σ
g : ; x| 1) (20 1+
rE((]
(a) = o a.
det log(d) + 1122)
log
dct(Ext)
39

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. The proof of this lemma is following an analogous approach as in Lemma 5.2 of [Zhou et al. 2020 Recall that we have the combination of reward estimation and the UCB being FA(2: f(:;; (
(t-1(a) Vo(z: (All-)))) O ( Meanwhile, consider an alternative being
Fa(x)) = (g(x;; [ - + + V /((a; ( ale--)
(g(z; O4 9
max OxEL--1
where we also have the outpul difference Fa(=)
/log(m)(2/3x_222 based on Lemma Fa(x)] & <0mm=1/o/lg(m
J.8 Afterwards; with Lemma J.1 and Lemma L.4 we will also have O E E--1, and the objective can
therefore be transformed into
(a( ( s (mx) - (xx)) + 0 1/6 213
max θx
(g(00 ( ( ---
(g(2;;; (o(z:;10AAcca
-
+0 1/6 2
221 0 1/6 /lggmm)(t//>-//
= =|e max
(9(2;) ( θ 0 (0(æ;; ( θ [0A|c-1)|
+0 1/6 log 2 ((5m 1/6
1 Iog(m) /6 11/6 [
< (g (9 - Vm (||) - | + max
|0 - (l 1)
+0 1/6 //mm-//6/oggmmm lm 2/3 2,3 O 1/6 /o0g(m)///0-118871
< 2 (a) (1))
ml - + (m 21 -
O05m 1/6 (m) 2
where the second inequality is by applying the Holder's inequality, and the last inequality is by applying Lemmas Lemma 5.2 in (hou et al. 2020), Lemma J.1 in terms of the confidence set E
Apart from this lemma that bounds the UCB for the chosen arm Ut, we can also have the following corollary for the UCB of the imaginary shadow model (-). Here, with the optimal arm being x arg maX ha (x),, can bound the UCB for reward estimation [ - FA (=;)/; where have the shadow model FA trained with past optimal arms and their rewards "x,,rr>re(t-- Comparable to the sequence of chosen arms (mt)r)( The definition of (a)
Corollary 1.2. Suppose the an imaginary arm-level neural network SA(: (0 has been trained on the optimal arms and their rewards r with J-iteration GD and learning rate n. Similarly, ) is a L-layer FC network with width m, and suppose we have m, J, satisfying the conditions in Theorem 3.1 Then, with the probability at least 1 8, we will have
ha(=;) - Fx(x)) < 1a) | (0)k-1)/ (-) + O(m 1/6 (1og(m)2/3x2110 -23333) 2/3
+ +0mm 1/6 /60
where we have Fx1) = (z) (21--1) + (o:, and we also have UCB,(x;) = 26-1(a)
/o(0;;10))<-)) -- (+)
(0),--1), as well as
E = AI + Σ
g(x;; (0%1--1 (0;;:10;1111)
rEld
(a) o a. log
det(E;_1) det(AI)
2 log(() + X1/25)
40

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. The proof of this corollary is similar to that of Lemma L.1 Analogously, consider alternative of F)()) being
Fx(x)= = (g(æ;
- (0% +--1(0) - (0yle-)
= max
9 (xx 0 - (0,bo)
where we can also prove the output difference (x) - Fi(2)] & O(m
2/3 L3) with a similar approach as in Lemma J.8. Afterwards, with Lemma J.1 and Lemma T.4 we will also have @ E E We have E = { | e - & (a)) /m) being the confidence set centered around the parameters (0) trained by optimal arms and their rewards. Then, the objective can therefore be transformed into
[x]] ha(x))) < - + (0 (10
| (0llc1) vm (1@, (6% A
max
|0 - 10% )
+ 1/0 Vlg(() -00m=|//00mmm]]
O(Sm 1/6 (logmm (6 2//7)
$ (a) [1 [ | (1)
+ O(S 1/6 /m Om 1-m-1/6 1/6 [t
where the second inequality is by applying the Holder's inequality, and the last inequality is by applying Lemmas Lemma 5.2 in (Zhou et al., 2020), Lemma J.1 in terms of the confidence set of optimal arms E--1- This is because for a given sequence of arms, which can be chosen arms {æt} or the optimal arms {æth, we will be able to approximate the true reward mapping function and derive the confidence set for
1.1.2 Term 2:
Reward Gap
Next, proceed to give the following lemma for bounding the second term, (aa()t,) ha(
Lemma 1.3. Suppose the arm-level neural network fa(: (le--) has been trained on chosen amms and their rewards
1], with J J-iteration GD and learning rate n,. Meanwhile, fa(::0Ale (Oale-1) L-layer FC
network with width m. Suppose we have m, J. satisfying the conditions in Theorem 5.1 Then, with the probability at least 1 6, will have
h((())) - ha()))) < 2n-1(aa) |1 (0Al-1// + O0m 1/6 3 2/3
1/6 + OSm 1166 Vlog(m)) 1000m//m)0001111111 -
By definitions in Lemma
L4
we denote FA(x)) fa(# 10 + UCB,( and UCB, n-1(a))
V /o(a: ( 4 A)e-1), where
(a) 00 0 a log del(AI)
det(Ex-1) llog(0) + x
Proof. The proof of this lemma extends the proof of Lemma I.1 continue to apply the alternative of the arm-sclection mechanism as
Following the workflow in Lemma [.] we
FA(x) (g(x; ( 19 [OA]u) + )-)(a)) (0)e:()))e_)))) 190: A
max AEE
θ - A+
41

---

Published in Transactions on Machine Learning Research (01/2026)
where also have the output difference [F(x)) (((z)-FFllh -Fa(z) O0 1/6 /log(m)22/3) - based on Lemma Next, with Lemma we can transform our objective to
(mx))) ha(#;) = (m,) - ha(14)
$ (o(0)) @Alo), 00 (a - - (9(2)) ( OA))) 0. (Oxoo)
S (0ll-))) (0Alu) - (9(2)) (All-1))
(Oalo) 00Sm 10 1/6 /10g(m))
S max (9(0;)
(0 ( 1 - (0x|)) (g(mn) (0 A, (0n])) O0S 1/6 /log(m)(1/6X 1/6 1,2/7)
OxEL--1
= Fa())) (9(=;; | A (0 + 0 1/6 /
where the first incquality is due to Lemma second inequality is due to Lemma J.7 third inequality is due to the fact that θ E 1,,, and the final equality is due to the definition of Fa(.).
Next, by utilizing the relationship between the pulling mechanisms, we will have
F (g(an) (9)..1)) (+x)o) O(Sm 1/6 /
[ - - 00 /00
+ (oggmm)
$ {F(()) - + 00 \
- (0l))) + O(Sm 1/6 1/
where the first inequality is due the difference between F and the second inequality is due to the arm pulling mechanism that Fa(Z)) 2 FA())) Afterwards, with Lemma J.1 and Lemma J.6 will also have O E E,-1, and the objective can therefore be transformed into
F (at))) - hx(x))
< (A(())) - (xx)) + (m - 1/6 (log(m))933-2/3111
(g(æ;) ( -100))))
= max
1
200 0 10/6mm116660 1/6 //gg)
= max
14- - (g(a;; ( Al) 0 - 1
x
+ +0 1/6 log( 2 + O 1/6
log(m)t1/6 -//0
S |1 (0ll-1) إيع Vm (10, 0
max
|0 - 10
+0 1/6 1aa_://Voooggmm Llggmmmmmm/3/ 2/3 2/3 13) + O(Sm 1/6
< (a) 119(0;; (0) / / + 0m + /3 2
+ +0(Sm 1/6 (olSmm=
where the second incquality is by applying the Holder's incquality, and the last incquality is by applying Lemmas Lemma 5.2 in (Zhou el al. 2020), Lemma J.1 in terms of the confidence set E Finally assembling all the components will finish the proof.
1.2 Upper Confidence Bound for the Arm-level Reward Estimation
Recall that in the pseudo-code of our proposed framework HgN-Bandit (Algorithm I. we utilize the UCB as the exploration strategy for the arm-level model. Here, UCB essentially models the uncertainty of the reward estimation, and measures how much the reward estimation can possibly deviates from the ground-truth expected arm reward. In particular, with the arm-level reward estimation network fa(: aa), with small probability d > 0, recall that aim to have P ((f a h UCB.(.:)) S 6, where UCB,(.) refers
42

---

Published in Transactions on Machine Learning Research (01/2026)
to the UCB associated with the tunable exploration coefficient 2 0. Here, formulate the following lemma to derive the exact form of (-) The results in terms of the arm-level UCB will be used as the exploration scores for the arm-level recommendation (line 8-11, Algorithm [
Lemma I.4. Suppose the arm-level neural network fa(: (0al-1)) has been trained on chosen arms and their rewards {ær, brE(e--1 with J-ileration GD and learning rale n1. Meanwhile, fa(:; [ (l 1) is L-layer FC network with width m. Suppose we have m, J, satisfying the conditions in Theorem 5. 1 Then, given the candidate arm x E EVEE. Nox in the filtered candidate pool, with the probability at least
8, we will have
Ta(=;/OA)es ha(z)) S sm-1(a) (1((;; (0a)e 2, + O(Sm -1/6 /00
+ +0 1/6 (0m-1////oog/// /f 2
By definition in Lemma 1.4 and Theorem 5.1 we denote F Fa = f (wri AlI--1 + UxB,) where the
upper confidence bond UCB. = 1(-)(a) v g( 1 O - | (All-1), with the terms
Σ. + + Σ
g (++--) 9(2;;;
rE((]
1-1(a)= = o a
del(E, log(d) + 11/28)
log
det(AI)
wilh nelwork gradient veclor g(æ; AA) veel V aa) RPA.
Proof. Applying the Lemma J.1 we can transform the objective
ff((;; OA) hx))) = (z; (g(2; O Alo), θ - [0A]o}]
+ 1/6 +
< θ
//0gg(m)2//x-11/67 -1/6
fa a)) (9(2: (All [0Alo)]
+ (g(x: [0 (O^b)
+ O(m 1/6
1
where the first equality is to Lemma J.1 the first incquality is duc to Lemma J.7 and Lemma J.1 and the last inequality is because of the triangular inequality. Then, we proceed to separately bound the first and second term on the RHS. For the first term, we will have
[<( (Q1)--1) - (g(a;;
= [a(;;; fa: - (():))))) (0A)))
S O0 2333
where the first equality is due to the fact that fa 1 Alu) 0 based on our parameter initialization approach,
and the inequality is by applying Lemma J.8 and Lemma J.6 Then, for the second term, we will have
Kg(x; [0a)
(Aalo) (g(a: e ( @ - (9
(g(æ; [0)]-1), - (-A|=-))
<
/ ب, v | || |
- )-) || O (0l-1)///lll
where the first inequality is by applying the Holder's 's inequality, and the last inequality is by applying Lemmas Lemma 5.2 in (Zhou et al. 2020), Lemma J.1 in terms of the confidence set E, and the fact that θ E E,-1. Finally, asscmbling all the components will finish the proof.
43

---

Published in Transactions on Machine Learning Research (01/2026)
J Lemmas For Arm-level Neural Networks
Similar to the category-level models, also apply the FC network for the arm-level prediction model. But, since we are applying different initialization approaches for category-level model and arm-level model respectively, the neural network behavior will diverge. Analogously, given the input feature vector a E RRd we denote the L-layer FC neural network with network width m by
T-1 Oz I D.O)) x,
(13)
1=1
where with & being the ReLU activation, we define the intermediate hidden representations h1 I E . L-1} 88
ho = 2, h4 = (( [1- and we also have the binary diagonal matrix functioning as the ReLU activation being
Dj = (iiia((((chh-DD.....HHhhhhhabaa
-1..
where I[-) is the indicator function. Afterwards, the corrosponding gradients will naturally become
Vo, = h h [e
(14)
For the arm-level model fA, for E [L - 11, each entry of θ is drawn from the Gaussian distribution [(0,, 2/m);; Each entry of O is drawn from the Gaussian distribution V(0,1/m).
J.1 Theoretical Results with NTK Gram Matrices
To begin with will first introduce some results, in order to link the NTK matrices (Def. 1 and Def. 2 with the reward mapping function h(-) and the gradient covariance matrix E (Algorithm D.
Lemma J.1. There erist positive constant C 0 such that with probobility at least 6, if network width satisfies the condition in Theorem 5.1 for any Ar, there exists a set of paramelers O such that
h(xx) (g(ar; On), θ Oo)
(15)
where parameters θ satisfy |1 - Ooll < 5//m, along with the NTK norm 2 2h MaaM-Mih -h, where the expected reward vector h [h(x)) E R BlArT.
The proof of this lemma is inspired by that of Lemma 5.1 in (Zhou et al. 2020). However, we build proof upon the non-duplicate arms Ar and the corresponding NTK Gram matrix M (Def. 2 instead of imposing the full-rank assumption on the conventional NTK matrix M (Def. 1. Here, recall that the matrix M is naturally positive definite (An Amin > 0), it is the NTK Gram matrix built upon set of distinct arms.
Proof.
Then, consider the gradient matrix with no-duplicate arms = [g(æ; Ou)l (ellle////// R where represents the total number of parameters in the neural network. As a result, by applying conclusion from Lemma J.3 and due to the fact that [Arl < 3T, with the network width m 2 2(L6 Log(TL/ Ve > 0 and the probability at least 1 6, we will have
Ş - M/ & E.
3p By setting e 2|Ar|"
we will have
GG = M G MMIMM M X./2I M/2 0.
44

---

Published in Transactions on Machine Learning Research (01/2026)
where the last two inequalities are due to the fact that M = AxI 0. Analogous to Lemma 5.1 in (Zhou et al. 2020). we consider the singular value decomposition of G being G = PAQT, where we naturally have A since M is positive definite. Then, with the expected reward vector h (Def. 2 we have
h (QAPT) (PÂ-'QT) h vm GT( Oa)
by considering there exists a set of parameters θ O + (PA (PA-1QT) h//m Therefore, since h m G Ob), we will have Vo Ar: h(x) (g(2; Ob) e Oa)
Mcanwhile, since GTG ž M/2, we will have the Euclidean distance
m | - . 1 - hT -
2
Finally, since the above results holds Vo År, due to the fact that Ar contains all the unique arms of the collection Ar, will directly have the above results regarding parameters @ feasible Vo Ar. This completes the proof.
Suppose the gradient. matria with vandomly initialized parameters ( XI EeEA g(x; Qn) g( T upon an arbitrary subset C Ar of arm collection Ar. With probabilily at least ô over the initialization, the resull holds:
Lemma J.2. Suppose m. salisfies the condilions in Theorem 5.1
det Σ())
log
det AI s d'lo(1++T]) +
Proof. First, recall that have Ar the collection of: (i) the chosen arms (ax) (ii) the optimal arms { (iii) and the imaginary ones { chosen by the corruption-fi -free model. This makes its cardinality |Ar| = 37. Thus, for the left hand side, we have
det ((0)
log
det(AI) < log deI + Σ g(æ; Oo)g(a; 2a) = det G.
ΦEAr
where we define gradient matrix Go - [g(o;; Oo) AE
Px Here, based on Lemma J.3 we can
bound the distance between the Gradient matrix product G Go and the NTK matrix M (Def. as
GGGG. M| < 3T
3T (TVO////) O(VT/2)
by setting 37 O(VT/A) (((L)) (TgTT//))))
The above results will hold, as long as we have the network width m matching the conditions in Theorem 5.1 As a result, we can have
log de Go/
log det H/X+ (GJG, -)
< log det(I + (I- H)/A)
< log det(I+ ||00(-/--|||||||0---~~~~>>>1>1
H|
det + + H
< det H/A)) +1
= dlog(1 + TKKA) +1.
The first inequality because the concavity of lotd)(() function: The third incquality due to || HA)-= < || < VT; The fourth inequality is by applying the above distance upper bound |
45

---

Published in Transactions on Machine Learning Research (01/2026)
M| O(VT/A) The last inequality is because of the choice the m; The last equality is because of the Definition of The proof is completed.
Lemma J.3. With the randomly initialized network parameters Ou RR and a collection of arms A R define the gradiend malria G [g(;;; Oo]lmEA Rex|Ai, Following the recursice procedure in Def. construct the NTK Gram matrir MA based arms A. Then, with the probability at least 1 1- 8, we will have
| - MAlle $ |A
with the nelwork width m (21 log (o1((()11/))/e))
Proof. The proof of this lemma is analogous to the proof of Lemma B.1 in (Zhou et al. 2020 Based Theorem 3.1 from (Arora et al. 2019h, we have that for any two arms 2, x' E A, if the network width m 2 Q2 log( L/ we will have (g(;;; g(), Ou)) - MA(æ, x'I| S where MA(æ, x') represents the element in NTK Gram matrix M, that corresponds to arms a and x'. Next, taking the union bound over all the arms in A, we will have
G MAIL==
ΣΣ B'A
Kg(æ; Oo), Ool)/m MM s |A) cc
as long as the network width m 2 (og[ooog((A(//6////
J.2 Additional Theoretical Results under Over patepaaramtttiiiaionn
Lemma J.4. There exist a positive constant O such that with probability at least 1 8, if m N CT L for any x E Ureng X,, there erists of parameters such that with the neural parameters , trained {0, )==1 we have
(g(x; Oo). θ - Oo) (g(x; ., Q 000 S O(S0 1/6 /l
where parameters satisfy || Ool < 5/ Mm, > 0 as shown in Lemma J.1
Proof. This lemma is based on Lemma Hore, our objective can be reformed into
Kg(x; Op), θ @u) (g(x: ② 11), @ θb)l = 0 - (o(x; Ou) -a(x; 0
s S/ /m (g(x: O.) 0(-;))))
< O(Sm 1/6 Vog(m)) 100(m))100>1100777
where the first inequality is due to Lemma and the second inequality due Lemmas J.5 J.6 and
Lemma J.7
Lemma J.5 (Lemma B.3 in Cao & Gu 2019
There exist constants {C.) such that for any ó 0, if
have
w S L ()ogm)- 3/2 -3/2
then, with probability at least 1 1- 5, for any
Lemma J.6 (Lemmna B.2 in (Zhou ||0 Ool S w and x, E (xi)T=1 we have 11g(2;; θ) S C2 mL
2020 For the L-lager full- cull-connected network f trained with
J-iteration GD, there erist constants {C 2 such that for 8 > 0, for all t (T), ; n, satisfy
2 2 C1m-3:mmm 3//2 3/2 log (TL2/5)33/2
2/t/(mXX) s C2 min 6 [log m]
3/2 (m(An)) - 6, 1-og='(logm) (logm) -133/88
n 3 Cs(md + tmL)
1/6 2 C. 1/
vt/x),
46

---

Published in Transactions on Machine Learning Research (01/2026)
then, with probobility at least 1 - 8, have
||0 Ooll s 2
||0 O 6 S (1 11-171 mmmA) /1/(m)) + C6m 2/3 O/m-2// VlogmL x 518 1 + v(/A).
Lemma J.7 (Theorem 5 in (Allen- Zhu al. C1, C2 such that if w S C₁ T. "og m, for
2019 With probability at least 1 6, there crist constants
+ Ool1 S w, we have
[ .₂ - g 00)1 S C2 lloologmu log 1/3 L (0 00)l22
Lemma J.8 ( [Lemma 4.1 in |Cao & Gu if T salisfies that
2019 ) There exist constants {Ch-1} 2 such that for any 6 2 0,
S C₂L 0 ml 3/22
then with probability at least 1- 1-8, 6, for all @ e satisfying || - -oll 0 Oul S and for any at E (=r we have
((; - f(x; 0²) - ((g(2; 0²) @² 0dII S 0/74/3 m log
Lemma J.9 ( Lemma 11 in (Abbasi- Yadkori et al.
2011 Lemma B.7 in Zhou et al. 2020 ). Suppose a
sequence of arms (e(t), with an arbitrary arm x is denoted by E, A1 Erej g( .r-
Xx from each time step t E [8]. The gradient matrix
(...)))))) -g(0;; O -1)T //m. Then, we can have
det Ee) det(AI)
Σ min (lo(az;0-~/// Tl|d
1] s 2
Lemma J.10. Suppose m satisfies the conditions in Theorem 5. Suppose the gradient matrix can be (2), O.-1)T/m, with the arm Fe,t E ( 2; from each time (8) 0,-1) g( represented by E AI Every g(
step t. With probability at least ó over the initialization, the result holds:
| W O(TLL)
F S 0(m 11/6
1/6 L.5,/1) 1/6)
det Σ del (AI)
det (z)))
log
log
< O(m 1/6 [logmm)($000 2/56/6 1/6)
del(AI)
where the matrix with randomly initialized parameters is [() AI Σ
LE(T g c,ti Oo) g( 0o)
Proof. Based on the Lemma J.5 for any E [T], (1 c 0o)ll - O(VmL). Then, for the first item:
T
[ 1| = ||AI+ + Σ
g( 0.65 @n)g(x (0) T/ml/2
T
||AT||2
g
ga
c
Op)g(a (8) 2o)
X
Σ
Oo)\vml <X+O(TT).
Then, the second and third inequalities in this lemma the direct. application of Lemma B.3 of Zhou et al. 2020 The proof is completed.
47


Reviews:
[{"review_id": "pEclgNm4O8", "reviewer": "Reviewer_5nwy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel bi-level hierarchical neural contextual bandit algorithm H_2N-Bandit for online recommendation system. The proposed framework aims to mitigate the huge computational cost incurred in traditional neural contextual bandits, where the computational cost scale as O(K) with K being the number of arms. The hierarchical approach adopted consists of two levels: a category-level recommendation at the outer level where a set of arm categories are first recommended, and an arm-level recommendation at the inner level, where the optimal arm is selected from the pre-filtered set of arm categories. Theoretical guarantees are provided for overparameterized neural models, which scale similar to the conventional neural bandits, but at far reduced computational time. Extensive experiments have been provided.\n\nThe paper is very clearly written, and is easy to read and understand. However, some points need further clarification, which I list below.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Rigourous theoretical proofs are provided, along with extensive experiments on MovieLens, Yelp and Amazon experiments.", "audience_yn": "Yes", "audience_explanation": "Yes, using neural network models for highly non-linear reward function has been of interest for quite some time, with several works. The critical challenge here is the computational complexity associated with the online learning. This paper presents a hierarchical model for contextual neural bandit learning that can address the computational challenges, with similar regret guarantees.", "requested_changes": "The regret bound in Theorem 5.1 is shown to scale similarly as in conventional neural bandits. It is good to explain how the effective dimension is affected when operating with almost 3T arms, at least experimentally. Further more, it is not clear what  denotes in the theorem and how it scales with T.\nThe algorithm now leverages three overparameterized neural networks that need to be trained. In particular, the network f_C^2(\\cdot) takes in input gradients from the first network f_C^1, whereby the input dimension scales with the number of parameters. How do these contribute to the computational complexity, in comparison to the conventional neuralUCB?\nHow is exploration and exploitation trade-off implemented at the category level recommendation?", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "z46eBHboWn", "reviewer": "Reviewer_gBv8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a bi-level hierarchical neural contextual bandit (“H2N-Bandit”). It first scores and selects a small set of promising categories, then chooses an arm only within those categories. Category “reward” is defined as the class’s best arm, aligning the category decision with the final arm decision. A UCB-style uncertainty term at the arm level and a pseudo-reward for categories enable end-to-end training. The authors provide regret bounds and show competitive regret with notable speedups on standard recommendation datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims made in the submission are supported by accurate, convincing and clear evidence.", "audience_yn": "Yes", "audience_explanation": "Researchers in online learning and bandits will likely be interested in this paper.", "requested_changes": "See additional comments", "broader_impact_concerns": "No specific broader impact concerns identified; the work is an algorithmic refinement with a risk profile similar to existing contextual bandit methods.", "additional_comments": "**Strengths.**\n\n* Clear motivation for large-K settings; the category→arm decomposition is natural and practically useful.\n* Objective alignment (class reward = within-class max) is thoughtful and well-argued.\n* Theory mirrors the two-stage design and helps justify the approach; empirical results indicate meaningful runtime gains.\n\n**Weaknesses.**\n\n* The pseudo-reward (max of prediction + UCB within a chosen class) risks optimism feedback and biasing the category model, while unchosen classes receive little corrective signal.\n* Category representations (mean/std of contexts) may miss rare, high-value arms; stronger set encoders or quantile/top-k features could help.\n* Some assumptions (over-parameterization, class-margin conditions) are strong; the dependence of network width/complexity on K needs clearer discussion.\n* Limited ablations on (i) category features, (ii) removing the exploration head, and (iii) robustness to noisy/overlapping categories and very large K.\n\n**Questions for authors.**\n\n1. How sensitive is performance to B, and do you have curves showing when the optimal class consistently enters the shortlist?\n2. What numerical safeguards are used for the arm-level UCB (e.g., covariance updates, regularization)?\n3. Does injecting conservative pseudo-labels for a few non-selected classes reduce optimism bias?\n\n**Suggestions.**\n\n* Add ablations on category encoding and the exploration head; test robustness to perturbed/merged categories.", "extra_scores": {}, "extra_text": {}}, {"review_id": "xvK4w1ww3q", "reviewer": "Reviewer_rT1b", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces $\\mathrm{H}^2\\mathrm{N}$-Bandit, a bi-level hierarchical neural framework for stochastic contextual bandits in online recommendation systems. It exploits arm category information (e.g., genres in MovieLens) to first select $B$ promising categories via neural exploitation/exploration nets, then recommends arms within the filtered pool using UCB. Pseudo-rewards from arm UCB train category models, enabling efficient exploration without true labels. Contributions: (1) Bi-level neural formulation for arbitrary rewards; (2) First stochastic hierarchical neural bandit regret bound $\\tilde{O}(\\sqrt{T \\tilde{d}})$ and category selection guarantee (Theorems 5.1-5.2); (3) Experiments on 3 datasets showing superior performance and runtime against 9 baselines; (4) Extension to three-level hierarchies. Overall, the authors have provided a very well written paper, with extensive theoretical grounding, and comprehensive experimental investigation. Solid work.", "claims_and_evidence_yn": "Yes", "claims_explanation": "- **Theoretical Support:** Claims of $\\tilde{O}(\\sqrt{T \\tilde{d}})$ regret (Sec. 5) are rigorously derived via NTK/martingale, handling arbitrary rewards without priors (novel vs. linear hierarchies like Hong 2022); category guarantee (Theorem 5.2) under mild $\\zeta$-margin; Comprehensive proofs in appendix\n- **Empirical Validation:** Experiments (Sec. 6) convincingly show lower runtime vs. baselines on 3 datasets (Figs. 1-3, Tables 1-2) while competitive or outperforming in regret; further experiments confirm bi-level value (e.g., no category exp. worsens performance).\n- **Clarity:** The whole paper: formulation, theoretical analysis and empriical results are clear and precise", "audience_yn": "Yes", "audience_explanation": "TMLR's RL and bandit theory audience would greatly value this work. Also potentially appealing to recsys communities.", "requested_changes": "None", "broader_impact_concerns": "None", "additional_comments": "The $\\mathrm{H}^2\\mathrm{N}$-Bandit framework shines on computational efficiency, but could sample efficiency be improved? Could latent bandits ideas (e.g., Hong et al. 2020) be integrated to infer hidden states within categories, potentially helping with sample efficiency by modeling latent user preferences?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)