Neural Collaborative Filtering Bandits via Meta Learning
Authors: Yikun Ban
Yunzhe Qi
Tianxin Wei
Jingrui He
Venue: Submitted to ICLR 2023 (2023)
Keywords: Neural Contextual Bandit
Meta Learning

Abstract: Contextual multi-armed bandits provide powerful tools to solve the exploitation-exploration dilemma in decision making, with direct applications in the personalized recommendation. In fact, collaborative effects among users carry the significant potential to improve the recommendation. In this paper, we introduce and study the problem by exploring `Neural Collaborative Filtering Bandits', where the rewards can be non-linear functions and groups are formed dynamically given different specific contents. To solve this problem, we propose a meta-learning based bandit algorithm,  Meta-Ban (\textbf{meta-ban}dits), where a meta-learner is designed to represent and rapidly adapt to dynamic groups, along with an informative UCB-based exploration strategy. Furthermore, we analyze that Meta-Ban can achieve the regret bound of $\mathcal{O}(\sqrt{nT\log T})$, which is sharper over state-of-the-art related works. In the end, we conduct extensive experiments showing that Meta-Ban outperforms six strong baselines.

Under review as a conference paper at ICLR 2023
NEURAL COLLABORATIVE FILTERING BANDITS VIA META LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Contextual multi-armed bandits provide powerful tools to solve the exploitation- exploration dilemma in decision making, with direct applications in the personal- ized recommendation. In fact, collaborative effects among users carry the signif- icant potential to improve the recommendation. In this paper, we introduce and study the problem by exploring 'Neural Collaborative Filtering Bandits', where the rewards can be non-linear functions and groups are formed dynamically given dif- ferent specific contents. To solve this problem, we propose meta-learnnn based bandit algorithm, Meta-Ban (meta-bandits), where a meta-learner is designed represent and rapidly adapt to dynamic groups, along with an informative UCB- based exploration strategy. Furthermore, we analyze that Meta-Ban can achieve the regret bound of O(vn' T),, which is sharper over state-of-the-art related works. In the end, we conduct extensive experiments showing that Meta- Meta-Ban outperforms six strong baselines.
INTRODUCTION
The contextual multi-armed bandit has been extensively studied in machine learning resolve the papliitttio-exploraiaii dilemma in sequential decision making, with wide applications in personalized recommendation (Li et 2010), online advertising eWu 2016), etc.
Recommender systems play an indispensable role in many online businesses, such as e-commerce platforms and online streaming services. It is well-known that user collaborative effects are strongly associated with the user preference. Thus, discovering and leveraging collaborative information in recommender systems has been studied for decades. the relatively static environment, e.g., in movie recommendation platform where catalogs are known and accumulated ratings for items are provided, the classic collaborative filtering methods can be easily deployed (c.g., matrix/tensor factorization (Su and Khoshgoftaar 2009)). However, such methods can hardly adapt to more dynamic settings, such as news or short-video recommendation, due to: (1) the lack of cumulative interactions for new users or items; (2) the difficulty of balancing the exploitation of current user-item preference knowledge and the exploration of the new potential matches (e.g., presenting new items to the users).
To address this problem, a line of works, clustering of bandits (collaborative filtering bandits) (Gentile Gentile et al. 2017 Li 2019 Ban and He| [022). have been proposed to incorporate collaborative effects among users which are largely neglected by conventional bandit
al. 22044 Li 20166; Gentile
algorithms (Dani et al., 2008 Abbasi-Yadkori Yadkori et al. 201T Valko et al. 2013 Ban and He 2020). These works use the graph- based method to adaptively cluster users and explicitly or implicitly utilize the collaborative effects on user sides while selecting an arm. However, this line of works have significant limitation that they all build on the linear bandit framework Yadkoi- et al.) 2011)
and the user groups are represented by the simple linear combinations of individual user parameters. The linear reward assumptions and lincar representation of groups may not be true in real-world applications (Valko et al. 2013).
To learn non-lineal reward functions, neural bandits (Collier and Liorens 2018 Zhou al. 2020
Zhang et al. 2021 Kassraie and Krause 2022) have attracted much attention, where a neural network assigned to learn the reward function along with exploration strategy (e.g., Upper Confidence Bound (UCB) or Thompson Sampling (TS).. However, this class of works do not incorporate any collaborative effects among users, overlooking the crucial potential in improving recommendation.

---

Under review as a conference paper at ICLR 2023
In this paper, to overcome the above challenges, we introduce the problem, Neural Collaborative Filtering Bandits (NCFB), built on either linear or non-linear reward assumptions while introducing relative groups. Groups are formed by users sharing similar interest/preffeennesshheee
However, such groups are usually not static over specific contents (Li et al. (016)) For example, two users may both like "country music" but may have different opinions on "rock musie". "Relative groups" are introduced in NCFB to formulate groups given a specific content, which is more practical in real problems.
To solve NCFB, we propose a meta-learning based bandit algorithm, Meta-Ban distinct from existing related works (i.e.. graph- based clustering of linear bandits (Gentile al. 2014 Li et al., 2016)) Gentile et al.] 2017 Li et al. 2019 Ban and He 202I)). Inspired by recent advances in meta-learning (Finn et al. 2017; Yao et al. 2019), Meta-Ban, meta-learner is assigned to represent and rapidly adapt to dynamic groups, which allows the non-linear representation of collaborative effects. And user-learner is assigned to each user to discover the underlying relative groups. Here, order to learn linear or non-linear reward functions. To solve the exploitation-explrratiie in bandits. Meta-Bat Ban has an informative UCB-type exploration. In the end, provide rigorous regret analysis and empirical evaluation for Meta-Ban. To the best our knowledge, this is the first work incorporating collaborative effects in neural bandits. The contributions of this paper can be summarized as follows:
neural networks to formulate both meta-learner and user learners, in
dilemma
(1) Problem. We introduce the problem, Neural Collaborative Filtering Bandits (NCFB), to incorpo- rate collaborative effects among users with either linear or non-linear reward assumptions.
Algorrit,,. We propose a meta-learning based bandit algorithm working in NCFB, Meta-Ban, where the meta-learner is introduced to represent and rapidly adapt to dynamic groups, along with a new informative UCB- -yyp exploration that utilizes both meta-side and user-side information. Meta-Ban allows the non-linear representation of relative groups based on user learners.
(3) Theoretical analysis. Under the standard assumptions of over per-paaramttrrieed neural networks, we prove that Meta-Ban Ban can achieve the regret upper bound of complexity O (Vn'l' log T), where n the number of users and T the number of rounds. Our bound is sharper than existing related works. Moreover, we provide a correctness guarantee of groups detected by Meta-Ban.
(4) Empirical performance. We evaluate Meta-Ban on 10 real-world datasets and show that Meta-Ban significantly outperforms 6 strong baselines.
Next, after introducing the problem definition in Section we present the proposed Meta-Ban in Section 3 together with theoretical analysis in Section In the end, we show the experiments in Section 5 and conclude the paper in Section 6 More discussion regarding related work is placed in
Appendix Section
A.I
2 NEURAL COLLABORATIVE FILTERING BANDITS
In this section, we introduce the problem of Neural Collaborative Filtering Bandits, motivated by generic recommendation scenarios.
Suppose there are n users, = [1, ........i] n). to serve on a platform. the 7th round, the platform receives user u, N and prepares the corresponding l arms (items) X, X1, .., X(,k) in which each arm is represented by its d-dimensional feature vector Xx, E RRd Vi E {l....,,k} k}. Then, like the conventional bandit problem, the platform will select an arm X;, E X, and recommend it to the user 24. In response this action, 24 will produce corresponding reward (feedback) rt,i- We use rt.a [ to represent the reward produced by 4 given Xt,5, because different users may generate different rewards towards the same arm.
Group behavior (collaborative effects) exists among users and has been exploited in recommender systems. In fact, the group behavior is ftem-nayying i.e., the who have the same preference on a certain item may have different opinions on another item (Gentile et al. 2017 Li et al. 2016). Therefore, we define relative group as of users with the same opinions on certain item.
2

---

Under review as a conference paper at ICLR 2023
Definition 2.1 (Relative Group). In round given X X,, relative group (xx..;) S N with respect to Xt,; satisfies
1) Vu, u' E ((r,.)), = B[redlu
2) A" = N.t. satisfies 1) and (xs,)) C.N.
Such flexible group definition allows users to agree on certain items while disagree on others, which consistent with the real-world scenario.
Therefore, given an arm Xt.i. the user pool N can be divided into gr,i non-overlapping groups: Ni N2 (xx,)), , N (x,,).. where qr n. Note that the group information unknown to the platform. We expect that the users from different groups have distinct behavior with respect to
Xt.i- Thus, we provide the following constraint among groups
Definition 2.2 (y-gap). Given two different groups N (xx,)). N" (xt,)) there exists constant y 0, such that
Vu E (Xx,s), u' W Blrr. E Errr,a/u
For any two groups in N, we assume that they satisfy the ?-gaap constraint. Note that such an assumption is standard in the literature of online clustering of bandit to differentiate groups (Gentile ctt al. 2014 Li et al., 2016 Gentile et al. 2017 Li et al., 2019; Ban and He (021).
Reward function. The reward Fr, is assumed to be governed by an unknown function with respect to X given dy:
T Me = h., (xx,)) + Se,s:
where bu, is an either linear or non-linear but unknown reward function associated with ue and Cr.i
a noise term with zero expectation EE [[ = 0. We assume the reward rt, E [0, 1] is bounded, as
in many existing works (Gentile et al. 2014 2017 Ban and He 2021). l). Note that online clustering
of bandits assume hw, is a linear function with respect to Xx, (Gettile et al. 2014 Li et al. 2016
Gentile et al. 2017 Li al., 2019 Ban and He 202T).
Regret analysis. In this problem, the goal is to minimize the pseudo regret of T rounds:
R Σ Rlri - re ue]:
where r is the reward received in round and Efr"" [u,, X.) maxx,, hug (xt,i)-
The introduced problem definition above can naturally formulate many recommendation scenarios. For example, for music streaming service provider, when recommending a song user, the platform can exploit the knowledge of other users who have the same opinions on this song, i.e., all 'like' or "dislike" this song. Unfortunately, the potential group information is usually not available to the platform before the user's 's feedback. To solve this problem, we will introduce an approach that can infer and exploit such group information to improve the recommendation. in the next section.
Denote by [K] the sequential list {l,..., k}. Let be the arm selected in round t and r. be the reward received in round We use [xxll2 and ||x; ll to represent the Euclidean norm and Taxicab norm. For each user E N, let μº be the number of rounds that user has been served up to round 1, i.e., 14" Dt=n 1 (u, = u.. and T be all of u's historical data up to round I, ie., T," = {(x,, r7) : u, = u A E [t]]. m the width of neural network and L is depth of neural network in the proposed approach. Given group M, all it's data up to can be denoted by hT"" = (T,"lu E A.. We use standard O, θ and Ω to hide constants.
Notation.
PROPOSED ALGORITHM
In this section, we propose a meta-learning based bandit algorithm, Meta-Ban, to tackle the challenges
in the NCFB problem as follows: (1) Challenge (CI): Given an arm, how to infer a user's relative
group, and whether the returned group is the true relative group? (2) Challenge 2 (C2): Given a relative group, how to represent the group's behavior in parametric way? (3) Challenge 3 (C3): How to generate a model to efficiently adapt to the rapidly-changing relative groups? (4) Challenge (C4): How balance between exploitation and exploration in bandits with relative groups?
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1: Meta-Ban
T (number rounds), V, Ygrroup exploration parameter), a(exploration parameter), X(regularization parameter), (coonidennce level), J1 (number of iterations for user), J2 of iterations for meta), ?h (user step size), 1/2 (meta step size), L(depth of neural network). Initialize Oo: 0g o μő
Input:
Vu E N
Observe one data for each u E N
for / .... T do
Receive a user E N and observe & arms X; for E [k] do
Determine u, relative groups:
Ni, (x.,)) = (u [I((x,,; 0-11) - s(x, 02-131 S -
O = GradientDecent Meta (Nu, (x),)); Ox-1))
U,, = -xx,;; +a.
111
L+1
(t/
v8
22
Pt.
10
argie(k) max U.
11
Play X,,5' and observe reward Tt,5'
12
X Xt,6i Tt Tr,;; ; O O
13
14 Pi-1
u.
ur
0, = GradientDecent
O₂)
14
for N and u. + do
16
40 = 0p-1 pi 1--1
Meta-Ban has one meta-learner @ to represent the group behavior and n user-learners for each user {0")ueM) JueN, sharing the same neural network f. Given arm Xt, we use g(x,,;; (x 0) to denote the gradient of f for the brevity. The workflow of Meta-Ban is divided into three parts as follows.
respectively, {0"
Group inference (to C1). As defined in Section 2 each user u E N is governed by unknown function hy. natural use the universal approximator (Hornik et al. 1989), a neural network (defined in Section 4h. to learn hy. In round t [T]. let u, be the user to serve. Given
past data up to round E- 1, T we can train parameters ftr by minimizing the following loss: L (T,"1 0%) > (x,))eT, (x(x;; 0*)) - 2)
Let 0"= represent 8 trained with T in round t 1. The training of 6th can be conducted by (stochastic) gradient descent, e.g., as described in Algorithm
Therefore, for each E N, we can obtain the trained parameters 0% Then, given u, and an arm Xt.i, we return u 's estimated group with respect to arm X,,i by
No, (xr,s) = {u E N (x.,; 0F-1 (x 0%
7
where y E (0,, 1) represents the assumed gygaap and is tuning parameter to trade off between the exploration of group members and the cost of playing rounds.
Meta learning (to C2 and C3). In this paper, we propose to use one meta-learner O to represent and adapt to the behavior of dynamic groups. In meta-learning, the meta-learner is trained based on a number of different tasks and can quickly adapt to new tasks with a small amount of new data (Finn et al. 2017). Here, consider each user N task and its collected data T," the task distribution. Therefore, Meta-Ban Ban has two phases: User adaptation and Meta adaptation.
User adaptation. In the tt round, given uy, after receiving the reward rt, have available data Th Then, the user parameter 8t is updated in round t based on meta-learner θ, denoted by 8 described in Algorithm
Meta adaptation. In the th round, given group Nu, (x,,), have the available collected data (Ti "e,,,, The goal of meta-learner is to fast adapt to these users (tasks). Thus, given arm Xt,i, update θ in round i, denoted by Or, by minimizing the following meta loss:
4

---

Under review as a conference paper at ICLR 2023
Algorithm 2: GradientDeeent__M Meta (N, .1-1)
(0) 0 (or (o) for j = 1,2, 1.2......J do J2
for u u NV do
Collect 7
Randomly choose T" _ T (0%;-)
=2 2 (f(; 04; ; r)
CN EvEN (Q + d
EnEr
(//1)
vm
6 (j-1) - 1/2 (0u. JueweN
P1-1
Return: O = (J2)
Algorithm 3: GradientDecent, User (u, θ2)
Collect T," # Historical data of u up to round
(%) O, (or Qa) for j -- 1,2,...,JJ J1 do Randomly choose Tu TT¹
L (Tu: 0r) (x (f(x; (f(x))) - r)2
0V (j-1) mn vo L. (Tu
Return: of (J.)
ym EneRa, (x..)) 100; |l1 where 0% Pi-1 the stored user parameters in Algorithm 3 at round - 1. Here, we add Ll-regularization on meta-learner to prevent overfitting practice and neutralize vanishing gradient in convergence analysis. Then, the meta-learner is updated by: θ = θ 122 Pue,,, (x,,)x,))" where 1)2 is the meta learning
N.,,, (x..) EneRi, (x..)) L (0p
A
p
rate and Viogy JueNN,, ()).) CW, (xe.)) is the sum of gradients of (i,,, with respect to all the
user learners in the group Ni,. Algorithm shows meta update with stochastic gradient descent (SGD).
Note that in linear clustering of bandits (Gentile al. 2014 cct al. 2019 Ban and He (021)) they represent the group behavior θ by the linear combination of user-learners, e.g., θ [W,, (x),:) ΣmeN.,
Li et al. 2016 Gentile al. 2017 Li
0% This may not be true in real world. Instead,
we use the meta adaptation update the meta-learner θ according to No, (x..), which can represent non-linear combinations of user learners (Finn et al. 2017: Wang et al. 2020b).
UCB Exploration (to C4). To balance the trade-off between the exploitation of the current group information and the exploration of new matches, we introduce the following UCB-based selection criterion. Based on Lemma C.2 with probability at least 6, after T rounds, the cumula-
tive error induced by meta-learner is upper bounded by Σ E [[[(x;; O.) rxl u.] s
rilx
(1lg(x;; O.) (xxr: 00 1ll) + EmEN 14
log(t/6)
where
Vi
22
Meta-side info
User-side info
(Xx; θx) incorporates the discriminative information meta-lcarner acquired from the col- laborative effects within the relative group Nu, (xx) and O ( shows the shrinking confidence
interval of user-learner to specific user u4. This bound provides necessary information we should include in the selection criterion (U,, in Algorithm [T.
which paves the way for the regret analysis (Theorem 4.2 Therefore, say that the bound U,, t, leverages both the collaborative effects existed
5

---

Under review as a conference paper at ICLR 2023
in Na. (x and ut's personal behavior for exploitation and exploration. Then, we select an arm according to: X = Ex,,, max
(U,,).
To sum up, Algorithm depiets the workflow of Meta-Ban. each round, given a served user and set of arms, we compute the meta-learner and its bound for each relative group (Line 5-9). Then, we choose the arm according to the UCB-type strategy (Line 10). After receiving the reward, we update the meta- meta-learner for next round (Line 12) and update the user-learner 6 (Line 13-14) because only U 's collected data is updated. In the end, we update all the other parameters (Lines 15-16).
Remark 3.1 (Time Complexity). Recall that is the number of users. It takes ((n) to find the group. Given the detected group Na. let b be the batch size of SGD) and J2 be the number of iterations for the updates of Meta-learner Thus, takes (IVV to update the meta-learner. Based on the fast adaptation ability of meta-learner, J2 is typically small number. b is controlled by the practitioner, and (. is upper bound by n. Therefore, the test time complexity is (12) - O(N, (bJ). In the large recommender system, despite the large number of users, given a serving user u, the computational cost of Meta-Ban is mostly related to the inferred relative group Nu. i.e., ( (J). Inferring Nr, is efficient because takes (nn) and only needs to calculate the output of neural networks. Therefore, as long as we can control the size of Nr, Meta-Ban can work properly. The first solution is to set the hyperparameter y to a small value, so [Vall is usually small. Second, we confine the size of [.Vu). i.e., we always choose the top- 100 similar users for u. With small size of Nu (I.al << n), Meta-Ban Ban can do fast meta adaptation to Nn, and make prompt decisions. Therefore, it is feasible for Meta-Ban to scale to large recommender systems, with some proper approximated decisions.
REGRET ANALYSIS
In this section, provide the regret analysis of Meta-Ban and the comparison with close related works. The analysis is built in the framework of meta-learning under the the over-parameterized neural networks regimen (Jacot et al. 2018 Allen-Zhu et al.) 2019 Zhou al. 2020).
Given an arm X E Rd with ||x,=||2 = 1, / E [7], i E [k]. without loss of generality, we define / as a fully-connected network with depth L 2 2 and width m:
f(x,; 0 or θ)
where is the ReLU activation function, W1 E mxd W Rax for 2 < 1 WL E 1x and 0, e = (W,,,,,),, veo (W2) ..... vec(WL)))] e R To conduct the analysis. we need the following initialization and mild assumptions.
Initialization. For I E [L- 1). each entry of W, is drawn from the normal distribution NN0, 2/ 2/m); Each entry of W, r, is drawn from the normal distribution ((011/m).
Assumption 4.1 (Arm Separability). For any pair Xt,i; xe. t, t' E &T),i, E [k), (t, + (t't)), these exists constant 0 < S ( such that [|x,, - xe l| 2 p.
Assumption is satisfied long as no two arms are identical. Assumption 4. is the standard input assumption in over- par-marrmeeeri neural networks (Allen Zhu et al. 2019). Moreover, most of existing neural bandit works (c.g., Assumption 4.2 in (Zhou et al. 2020)) 3.4 in (Zhang et al.) [0221) 4.1 in Kassraie and Krause 2022) have the comparable assumptions with equivalent constraints. They require that the smallest eigenvalue Ao of neural tangent kernel (NTK) matrix formed by all arm contexts is positive, which implies that any two arms cannot be identical. As L can be set manually, the condition 0 < p < O can be easily satisfied (e.g., L 2).
Then, we provide the following regret upper bound for Meta-Ban with gradient descent.
Theorem 4.2. Given the number of rounds T, assume that each user is uniformly served and set To TV, Vi E [T]. For any (0, < p S 0 < a < e2 1, > O, suppose

---

Under review as a conference paper at ICLR 2023
m, n1, 72, J1. J2 satisfy
m 2 52 max (ooly(T, L, L,p ".e""".evvoxxorT1) }). 111 poly(T, L)
P
Vmp
vpcz
J1 |poly(T, L)
72 min
log
(5)
T4L2m/
T²I.2Am?
p²
(T m)
C2 L
I (O m
J2 max
VRE2P
p62
Then, with probability least 1 over the random initialization, Algorithms has the following regret upper bound:
RT O(vn) (VT +TT+ LVT V (TT)) O().
Comparison with clustering of bandits. The existing works on clustering bandits (Gentile et al.) 2014 Li et al. 2016, Gentile et a 2017 Li et al.) 2019 Ban and He (02T) are all based on the linear
reward assumption and achieve the following regret bound complexity: Rx S Old I' log T).
Comparison with neural bandits. The regret analysis in single neural bandit (Zhou al. 2020
Zhang et al. 2021 has been developed recently (n = 1 in this case), achieving
R7 S OldVTlog T), d log det + H/A)
log + Tn/A)
where H is the neural tangent kernel matrix (NTK) Zhou al. 2020 Jacot al. 2018 and is regularization parameter. d is the effective dimension first introduced by Valko et (001)) to measure the underlying non-linear dimensionality of the NTK kernel space.
Remark 4.3 (Improve O (VlogT)) It is easy to observe that Meta-Ban achieves O ((V /VT log' 7),
improving by a multiplicative factor of OV T' over above existing works. Note that these works (Gentile et al., 2014: [i et al., 2016: Gentile et al., 2017: Li et al., 2019: Ban and He. 2021 Zhou ctt al. 2000: Zhang et al. 202 all explicitly apply the Confidence Ellipsoid Bound (Thcorem 2 in -Abbasi-Yadkori et al. 2011)) to their analysis, which inevitably introduces the complexity term
(log(T))) In contrast, Meta-Ba tan builds generalization bound for the user-learner (Lemma E.I). inspired by recent advances in werrpaarameterized network (Cao and Gu 2019). which only brings in the complexity term O (Vooog T). Then, we show that the estimations of meta-learner and user-learner close enough when 0 and θ are close enough, to bound the error incurred by the meta-learner (Lemma C.T.. Thus, we have a different and novel UCB-type analysis from previous works. These different techniques lead to the non-trine non-trivial improvement of O( T)).
Remark 4.4 (Remove Input Dimension). The regret bound of Meta-Ban Ban does not have d or d. When input dimension is large (e.g.. d Z T), may cause a considerable amount of error for RT- The effective dimension d may also incur this predicament when the determinant of H is very large. As (Gentile et al. 2014: Li et al.) 2016)] Gentile et al.) 2017 Li et al.) 2019: Ban and He 202 build the contidence ellipsoid for (optimal parameters) based on the linear function F
x (xt.2, 0*), their regret bounds contain d because of x,,; E Rdd Similarly, (Zhou 2020 Zhang et al. 2021 construct the confidence ellipsoid for 4* according to the linear et al.
function E[r,, xx,] = (g 0)), 0 6o) and thus their regret bounds are affected by d due to
g(Xe,;; 6o) E R (d reaches to in the worst case). On the contrary, the generalization bound derived our analysis only comprised of the convergence error (Lemma(D.) and the concentration bound (Lemma E.3 These two terms both are independent of d and d, which paves the way for Meta-Ban to remove the curse of d and d.
Remark 4.5 (Remove i.i.d. Arm Assumption). We do not impose any assumption on the distribution of arms. However, the related clustering of bandit works (Gentile et al. 2014 Li al. 2016 Gentile et al. 2017) assume that the arms are i.i.d. drawn from some distribution in each round, which may not be mild assumption. In our proof, we build the martingale difference sequence only depending on the reward side (Lemma E.3), which is novel, to derive the generalization bound of lear-learner and remove the i.i.d. arm assumption.
7

---

Under review as a conference paper at ICLR 2023
Relative group guarantee. Compared to detected group Nu. (xx,)) (Eq.3)) emphasize that Nu, (xx,i) (Ut Nu, (Xt,s) is the ground-truth relative group satisfying Definition 2.1 Suppose 7-gap holds among N, we prove that when is larger than constant, i.e. t 2 T (as follows), with probability at least 5, it is expected over all selected anms that Nu. (x,) S E.u.. (xx) and Na, (x+) = Nu. (x²) if 2 2. Then, for v, we have: (1) When 1, we have more chances to explore collaboration with other users while costing more rounds (T t); (2) When v 4, we limit the potential cooperation with other users while saving exploration rounds (T' L). More details and proof of Lemma 4.6 are in Appendix
Lemma 4.6 (Relative group guarantee). Assume the groups N satisfy "-gap (Definition and the conditions of Theorem 4.2 For any v > 1, with probability at least 1 over the random initialization, there exist constants 01, ,2, such that when
n64v2 (1++2(1+E5)) E2) (log 31+50) + 91 +2,
loog
4(1+2.)
TT
r2(1 + (og
given a user u E N, it holds uniformly for Algorithms 13 that
X (x,)) SN (x,)x)) and
(N((x,) =N, 22
where X is uniformly drawn from Te x and T," x (x+ :u -uAre E [d] is all the historical selected arms when serving u up to round t.
5
EXPERIMENTS
Peal and Mitreet
1380
BOLL
GELL
1140
750
1000
1243 X030
1903 1960s 1991
1190
X063
20.22
3100
1150
1200
1250
152
2543
Figure Regret comparison on ML datasets (10 runs). Meta-Ban outperforms all baselines. Specifically, compared to the best baseline, Meta-Ban improves 26.2% 2 Mnist and Notmnist, 12.2% on Cifar10, 25.2 % on EMNIST(Letter), and 28.8% % on Shuttle.
In this section, we evaluate Meta-Ban's empirical performance ML and 2 real-world recommen- dation datasets, compared to six strong sate-of-the-ee baselines. We first present the setup and then the results of experiments. More details are in Appendix
ML datasets. We totally use 8 public classification datasets: Mnist (LeCun et al. 1998 Notmnist (Bulatov] 201T), Cifar10 (Krizhevsky et al. (209)), Emnist (Letter) (Cohen et al. (217)) Shuttle (Dua
and Graff (017), 7), Fashion (Xiao et 2017), Mushroom (Dua and Grafi 2017). and Magictelescope (Dua and Graff 2017). Note that ML datasets are widely used for evaluating the performance neural bandit algorithms (e.g., (Zhou et al. 2020; Zhang et al. 2021)), which test the algorithm's 's ability in learning various non-linear functions between rewards and arm contexts. On ML datasets, we consider to hold an exclusive reward function. As some classes have correlations, the goal of ML datasets also is to find the classes with strong correlations and leverage this information to improve the qualify of classification.
each class
8

---

Under review as a conference paper at ICLR 2023
Recommendation datasets. We alse two recommendation datasets for evaluation: Movielens (Hrrpr and Konstan 2015) and Yelp The descriptions are in Appendix A.2
Baselines. We compare Meta-Ban six State-Of-Ther
(SOTA) baselines follows: (1) CLUB
(Gentile ct al. 2014); (2) COFIBA (Li et al., 2016); (3) SCLUB (Li et al. 2019); (4) LOCB (Ban
and He 2021): (5) NeuUCB ONE (Zhou al. 2020); (6) NeuUCB-IND (Zhou al. 2020 See
detailed descriptions Appendix [A.2 Since LinUCB Li et al. (2010) and KernalUCB
Valko et al. (2013) are outperformed by the above baselines, do not include them in comparison.
Teattrr-Meat
Peat
CARIBA
LIRRA
LOCK
ALC
Founds
CONTA
CTRRL
Mate-te Dene
Mets
300
300
Regret comparison on ML datasets. Meta-Ban outperforms all baselines. Specifically, compared to the best baseline, Meta-Ban improves 41.6% % on Fashion-Mnist, 28.4% on Mnist, 47.1 % on Mushroom, and 61.5% on Magictelescope.
Figure 2:
Results. Figure 2 shows the regret comparison on ML datasets in which Meta- Ban outperforms all baselines. Each class can be thought of as a user in these datasets. As the rewards non-linear to the arms on these datasets, conventional linear clustering of bandits (CLUB, COFIBA, SCLUB, LOCB) perform poorly. Thanks the representation power of neural networks, NeuUCB-ON obtains better performance. However, it treats all the users as one group, neglecting the disparity among groups. In contrast, NeuUCB-IND deals with the user individually, not taking collaborative knowledge among users into account. Meta-Bas Bieta-Ban&ee significantly outperforms all the baselines, because Meta-Ban can exploit the common knowledge of the correct group of classes where the samples from these classes have non-trivial correlations, and train the parameters on the previous group to fast adapt to new tasks, which existing works do not possess. Figure 3 reports the regret comparison on recommendation datasets where Meta- Ban still outperforms all baselines. Since these two datasets contain considerably inherent noise, all algorithms show the linear growth of regret. As rewards are almost linear to the arms these datasets, conventional clustering of bandits (CLUB, COFIBA, SCLUB, LOCB) achieve comparable performance. But they still are outperformed by Meta-Ban because simple vector cannot accurately represent user's behavior. Similarly, because Meta-Ban can discover and leverage the group information automatically, it obtains the best performance surpassing NeuUCB-ONE and NeuUCB-IND, Furthermore, hyper-parameter sensitivity study is in Appendix A.3
CONCLUSION
In this paper, we introduce the problem, Neural Collaborative Filtering Bandits, to incorporate collaborative effects in bandits with generic reward assumptions. Then, propose, Meta-Ban to solve this problem, where a meta-learner is assigned to represent and rapidly adapt to dynamic groups, along with a new informative UCB-type exploration. Moreover, Meta-Ban and shows that Meta-Ban can achieve a sharper regret upper bound than the close related works. In the end, we conduct extensive experiments evaluate its empirical performance compared to SOTA baselines.
provide the regret analysis of
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Y. Abbasi-Yadkori, D. Pál. and C. Szepesvári. Improved algorithms for linear stochastic bandits, In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
Z. Allen-Zhu, Y. Li, and Song. convergence theory for deep learning via weerparramtteriztionn. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
R. Allesiardo, Féraud, and D. Bouneffouf. A neural networks committee for the contextual bandit problem. In International Conference Neural Information Processing, pages 374-381. Springer, 2014.
Y. Ban and J. He. Generic outlier detection in multi-armed bandit. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 913-923, 2020.
Y. Ban and J. He. Local clustering in contextual multi-armes bandits. In Proceedings of the Web Conference 2021, pages 2335-2346, 2021.
Y. Ban, J. He, and C. B. Cook. Multi-facet contextual bandits: A neural network perspective. In The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 18, 2021, pages 35-45, 2021a.
Y. Ban, Y. Yan, Banerjee, and J. He. Ee-net: Exploitaiion-explrraiio neural networks in contextual bandits. arXiv preprint
2021b.
Y. Bulatov. Notmnist dataset. Google (Books/OCR), Tech. Rep.[Online), Available: http://yaroslavvb. blogspot. it/201 1/2011//9/ntmmmisstdde datasse.. html, 2, 2011.
Y. Cao and Q Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 12:16666108846 2019.
G. Cohen, S. Afshar,, J. Tapson, and A. Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 international joint conference on neural networks (IJCNN), pages 2921-2926. IEEE, 2017.
M. Collier and H. Llorens. Deep contextual multi-armed bandits. arXiv preprint arXiv:1807.00m 1807.0989, 2018.
V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. 2008
A. A. Deshmukh, U. Dogan, and C. Scott. Multi-task learning for contextual bandits. In Advances in neural information processing systems, pages 4848-488 2017.
D. Dua and C. Graff. UCI machine learning repository, 2017. URL httt://archive.iee uci edu/ml
P. Dutta, M. Kit, J. S. Kim, M. Mascaro, al. Automl for contextual bandits. arXiv preprint 19Xvv:190.032//1 2019.
C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, pages 1136-1135. PMLR, 2017.
C. Gentile, S. Li, and G. Zappella. Online clustering of bandits. In International Conference on Machine Learning, pages 757-765, 2014.
C. Gentile, S. Li, P. Kar, Karatzoglou, Zappella, and Etrue. On context-dependent clustering of bandits. In Proceedings of the 34th International Conference Machine Learning-Voit -Volue 70, pages 1253-1262. JMLR. org, 2017.
F. M. Harper and J. A. Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis) 5(4):1-19, 2015.
Hong, B. Kveton, M. Zabeer, Chow, A. Ahmed, and C. Boutilier. Latent bandits revisited. Advances in Neural Information Processing Systems, 33:13423-13433 2020.
10

---

Under review as a conference paper at ICLR 2023
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks universal approxi- mators. Neural networks, (55):3593366 1989.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580 2018.
Y. Jia, W. Zhang, D. Zhou, Q Gu, and H. Wang. Learning neural contextual bandits through perturbed rewards. In International Conference on Learning Representations, 2021.
Kassraie and A. Krause. Neural contextual bandits without regret. In International Conference on Artificial Intelligence and Statistics, pages 240-278. PMLR, 2022.
N. Korda, B. Szörényi, and L. Shuai. Distributed clustering of linear bandits in peer to peer networks. In Journal of machine learning research workshop and conference proceedings, volume 48, pages 1301-1309. International Machine Learning Societ, 2016.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Y. LeCun, L. Bottou, Bengio, and Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2118:222333 2324, 1998.
L. Li, W. Chu, J. Langford, and R. E. Schapire. contextual bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
S. Li, A. Karatzoglou, and C. Gentile. Collaborative filtering bandits. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 539-548, 2016.
S. Li. W. Chen, S. Li, and K.-S. LLung. Improved algorithm on online clustering of bandits. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 2923-2929. AAAI Press, 2019.
Lipton, Li, Gao, L. Li, Ahmed, and L. Deng. Bbq-networks: Efficient exploration in deep reinforcement learning for task-oriented dialogue systems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
O.-A. Maillard and S. Mannor. Latent bandits. In International Conference Machine Learning, pages 136.144. PMLR, 2014.
C. Riquelme, G. Tucker, and J. Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. arXiv preprint ar arXiv:1802.09127 2018.
M. R. Santana, L. C. Melo, F. H. Camargo, B. Brandão, A. Soares, R. M. Oliveira, and S. Caetano. Contextual meta-bandit for recommender systems selection. In Fourteenth ACM Conference on Recommender Systemx, pages 444-449, 2020.
X. Su and T. M. Khoshgoftaar. A survey of collaborative filtering techniques. Advances in artificial intelligence, 2009, 2009.
M. Valko, N. Korda, R. Munos, I. Flaounas, and N. Cristianini. Finite-tinee time analysis of kernelised contextual bandits. arXiv preprint urXiv: (at::330966000 6869, 2013.
H. Wang, R. Sun, and B. Li. Global convergence and generalization bound of gradient-based meta-learning with deep neural nets. arXiv preprint arXiv:2006. /4606, 2020a.
L. Wang, Q Cai, Z. Yang, and Z. Wang. On the global optimality of model-agnostic meta-learning.
In International Conference on Machine Learning, pages 9837-9846. PMLR, 2020b.
J. Wu, C. Zhao, T. Yu, J. Li, and S. Li. Clustering of conversational bandits for user preference learning and elicitation. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2129-2139, 2021.

---

Under review as a conference paper at ICLR 2023
Q. Wu, H. Wang, Q. Gu, and H. Wang. Contextual bandits in collaborative environment. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 529-538 2016.
H. Xiao, K. Rasul, and Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms, 2017.
P. Xu, Z. Wen, H. Zhao, and Q. Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:2012.0/780, 2020.
L. Yang, B. Liu, L. Lin, F. Xia, K. Chen, and Q. Yang. Exploring clustering of bandits for online recommendation system. In Fourteenth ACM Conference Recommender Systems, pages 120- 129, 2020.
H. Yao, Y. Wei, J. Huang, and Z. Li. Hierarchically structured meta-learning. In International Conference on Machine Learning, pages 7045-7054. PMLR, 2019.
W. Zhang, D. Zhou, Li, and Q. Gu. Neural thompson sampling. In International Conference on Learning Representations, 2021.
D. Zhou, L. Li, and Q. Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 1 11492-1 11522. PMLR, 2020.
12

---

Under review as a conference paper at ICLR 2023
2003
Powetess
8000
Yelp
3803
183-
Figure 3: Regret comparison on recommendation datasets (10 runs). Meta-Bat outperforms all baselines. Specifically, compared to the best baseline, Meta-Ban improves 7.02% % on Movielens and 2.6% on Yelp.
A
SUPPLEMENTARY
In this section, we first introduce the related works and present the experiments setup coming with extensive ablation studies.
A.1 RELATED WORK
In this section, briefly review the related works, including clustering of bandits and neural bandits.
Clustering of bandits. CLUB Gentile et al. (2014) first studies exploring collaborative effects among users in contextual bandits where each user hosts an unknown vector to represent the behavior based on the linear reward function. CLUB formulates user similarity on an evolving graph and selects an arm leveraging the clustered groups. Then. Li et al. (2016); Gentile et al.) (2017) propose eluster users based on specific contents and select arms leveraging the aggregated information of conditioned
groups. Li al. (2019) improve the clustering procedure by allowing groups to split and merge. [ann and He (2021) ) use seed-base local clustering to find overlapping groups, different from globally clustering on graphs. Korda al. (2016): Yang et al. (2020); Wu et al. (202T) also study clustering of bandits with various settings in recommendation system. However, all the series of works are based on the linear reward assumption, which may fail many real- applications.
Neural bandits. Allesiardo et al. 2014) use neural network to learn each action and then selects an arm by the committee networks with e-greedy strategy. Lipton et al. (2018); Riquelme et al.) (2018) adapt the Thompson Sampling to the last layer of deep neural networks to sclect action. However, these approaches do not provide regret analysis. Zhou et al. (2020) and Zhang et al. (2021) first provide the regret analysis of UCB-based and TS- neural bandits, where they apply ridge regression on the space of gradients. [ann et al. (2021a) study a combinatorial problem in multiple neural bandits with a UCB-based exploration. Jia al. (202T) perturb the training samples for incorporating both exploitation and exploration portions. Mlt-NetBBnn et al., 2021b) proposes to use another neural network for exploration. Xu al. (2020) combine the last-layer neural network embedding with linear UCB to improve the computation efficiency. Unfortunately. all these methods neglect the collaborative effects among users contextual bandits. DDutta al. (2019) use an off-the- shelf meta-learning approach to solve the contextual bandit problem in which the expected reward formulated as Q-function. Santana et al. (2020) propose a Hierarchical Reinforcement Learning framework for recommendation in dynamic experiment, where a meta-bandit is used for the select independent recommender system. Kassraie and Krause (2022) revisit Neural-UCB type algorithm
and show the (T) regret bound without the restrictive assumptions on the context. Maillard and Mannor 2201 4); Hong et al. (2020) study the latent bandit problem where the reward distribution of arms are conditioned on some unknown discrete latent state and prove the Ö(T) regret bound for their algorithm as well.
Key Differences from Related Work. We emphasize that we made important improvements compared to each aspect. (1) Compared to (Gentile et al.) (017), the only similarity is that we adopt the idea of leveraging relative groups. (2) Compared to NeuUCB (Zhou et al., (020), in addition to the fact that they do not incorporate collaborative filtering effects, we have provided important technical improvements. The UCB in NeuUCB has to maintain a gradient outer product matrix (Z, in NeuUCB) which occupies space R (0 E R?), and only incorporates user-side information. The new UCB introduced our paper does not need to keep the gradient matrix and contains both gidup-side and user-side information. (3) Compared to (Wang et al. 2020a), achieved the
13

---

Under review as a conference paper at ICLR 2023
convergence of meta-learnrr in the online learning setting with bandit feedback, where need to tackle the challenge that the training data of each round may come from different user distributions.
A.2 EXPERIMENTS SETUP AND ADDITIONAL. RESULTT
ML Datasets. In all ML datasets, following the evaluation setting of existing works (Zhou et al. 2020; Valko et al., 2013 Deshmukh et al., 2017), we transform the classification problem into a bandit problem. Take Mnist as an example. Given an image x E Rd, it will be transformed into 10 arms, X1 = (x o......011 0) in sequence. The reward is defined as 1 if the index of selected arm equals x' ground-truth class; Otherwise, the reward is O. In the experiments of Cifar Emnist, and Shuttle, class as a user and randomly draw a class first and then randomly draw a sample from the class. Note that some classes have strong correlations and thus these datasets evaluate one approach's 's ability to detect and leverage these correlated classes. In the experiments of Mnist and Notmnist (in Figure []] we add these datasets together as these two both are 10-class classification datasets, to increase the difficulty of this problem. Thus, we consider these two datasets as two groups, where each class can be thought of as a user. In each round, we randomly select group (i.e., Mnist or Notmnist), and then we randomly choose an image from class (user). Note that we run all approaches on the Mnist as well (in Figure 2 only this time instead of on Mnist and Notmnist together (in Figure D..
xx- = (0, x
X2
x x matching 10 class 0) ...... X10 (0, ........ ......
consider each
Movielens (Harper and Konstan, 2015) and Yelp datasets. Moviel.ens is recommendation dataset consisting of 25 million reviews between 1.6 10" users and 10 movies. Yelp is a dataset released in the Yelp dataset challenge, composed of 4.7 million review entries made by 1.18 million users to 1.57 x 10t restaurants. For both these two datasets, we extract ratings in the reviews and build the rating matrix by selecting the top 2000 users and top 10000 cestaurant(movvis)) Then, we use the singular-vall vaauue decomposition (SVD) to extract a normalized 10-dimensional feature vector for each user and restaurant(movie) The goal of this problem is to select the restaurants (movies) with bad ratings (due to the imbalance of these two datasets, i.e., most of the entries have good ratings). Given an entry with specific user, we generate the reward by using the user's rating stars for the (msv))) If the user's rating is less than 2 stars (5 stars totally). its reward is 1; Otherwise, its reward is O. From these two datasets, as a single user may not have enough entries to run the experiments, we use K-means to divide users into 50 clusters, where each cluster forms a new user. Therefore, the user pool totally consists of 50 users for these two datasets. Then, in each round, a user to serve U, is randomly drawn from the user pool. For the arm pool, we randomly choose one restaurant (movie) rated from u, with reward 1 and randomly pick the other 9 restaurants (movies) rated by u, with 0 reward. Therefore, there are totally 10 arms in each round. We conduct experiments on these two datasets, respectively.
Baselines. We compare Meta-Ban to six Maate-O--The-ae (SOTA) baselines follows: (1) CLUB (Gentile et al. 2214) clusters users based on the connected components in the user graph and refine the groups incrementally. When selecting arm, it uses the newly formed group parameter instead of user parameter with UCB- -bsed exploration; (2) COFIBA (Li et al.) 2016) clusters on both user and arm sides based on evolving graph, and chooses arms using
exploration strategy; (3) SCLUB (Li et al. 2019) improves the algorithm CLUB by allowing groups to merge and split to enhance the group representation; (4) LOCB (Ban and He 202T) uses the seed-based clustering and allow groups to be overlapped, and chooses the best group candidates when selecting arms; (5) NeuUCB-ONE (Zhou al. 2020) uses one neural network to formulate all users and select arms via a UCB-based recommendation; (6) NeuUCB-IN to formulate one user separately (totally N networks) and apply the same strategy to choose arms. Since LinUCB (Li et al. 2010) and KernalUCB (Valko et al. 2013) are outperformed by the above baselines, we do not include them in comparison.
(Zhou et al. (0200) uses one neural network
Configurations. For all the methods, they all have two parameters: À that is to tune regularization at initialization and a which is to adjust the UCB value. To find their best performance, we conduct the grid search for À and a over (0.01, 0, 1) and (0.0001, 0.001, 0.01, 0.1) respectively. For LOCB, the number of random seeds is set as 20 following their default setting. For Meta-Ban, we set v as 5 and y as 0.4 to tune the group set. To compare fairly, for NeuUCB and Meta- Meta-Ban, use the same simple neural network with 2 fully-connected layers and the width m is set as 100. To save the
https: h/t::///wwwww hwwp//wwwwwooooo yew com/dataset
14

---

Under review as a conference paper at ICLR 2023
running time, train the neural networks every 10 rounds in first 1000 rounds and train the neural networks every 100 rounds afterwards. In our implementation, the gradient descent (Algorithm 2 and 3) stops when the training error is smaller than 0.001, but the J1 and J2 restricted by 1000. In the end, we choose the best results for the comparison and report the mean and standard deviation (shadows in figures) of 10 runs for all methods.
A.3 SENSITIVITY STUDY FOR AND 7
In this section, we conduct the ablation study for the group parameter v. Here, we set as fixed value 0.4 and change the value of to find the effects on Meta-Ban's performance.
4033
2800
3850
6000
10808
Figure 4: Sensitivity study for v/ on MovicLens Dataset.
Figure 4 shows the varying of performance Meta-Bat with respect v. When setting 1.1, the exploration range of groups is very narrow. This means, in each round, the inferred group size [W,, (x),)) tends to be small. Although the members in the inferred group Nu, (xt,s) is more likely to be the true member of u, 's relative group, we may lose many other potential group members the 5, the exploration range of groups is wider. This indicates have more chances to include more members in the inferred group, while this group may contain some false positives. With larger size of group, the meta-learner O can exploit more information. Therefore, Meta-Ban with 5 outperforms v = 1.1. But, keep increasing v does not always mean improve the performance. since the inferred group may consist of some non-collaborative users. bringing into noise. Therefore, in practice. we usually set as relatively large number. Even we can set v as the monotonically decreasing function with respect to l.
beginning phase. When setting
A.4 SENSITIVITY STUDY FOR a
1ree
0.22
2006
2008
Figure 5: Sensitivity study for on Mnist Dataset.
Figure the sensitivity of Meta-Ban with regard to a. Meta-Ban shows the robust performance as a is varying, which stems from the strong discriminability of meta learner and the derived upper bound. Despite that the magnitude of a is changing, the order of arms ranked by Meta-Ban is slightly influenced. Thus, the Meta- Ban can obtain the robust performance, alleviating the hyperparameter tuning.
A.5 ABLATION STUDY FOR INPUT DIMENSION
We run the experiments on MovieLens dataset with different input dimensions and report the results as follows. Table | the final regret of each method with different input dimensions (5 runs). Meta-Ban keeps the similar regret with the small fluctuation. This fluctuation acceptable given that different input dimensions may contain different amount of information. NeuUCB-ONE
15

---

Under review as a conference paper at ICLR 2023
and NeuUCB-IN BND also the neural network to learn the reward function, they have the similar property. In contrast, the regret of linear bandits (CLUB, COFIBA, SCLUB, LOCB) is affected more drastically by the imput dimensions, which complies with their regret analysis.
CLUB
COFIBA
SCLUB
LOCB
NeuUCB-ONE
NeuUCB-IND
Meta-Ban
I0 dim
6174.8
5040.4
6232.8
5499.3
4939.6
7491.0
4673
20 dim
6845.4
7726.0
6742.3
5828.6
5643.0
7888.4
5190.2
50 dim
7384.6
7804.2
7563.2
6030
5403.4
7239.0
5178.3
100 dim
7188
7877
7433.0
6354
5523.9
7991.1
5463.4
200 dim
7450.5
8463.5
7805.1
6674.3
5821.1
8032.6
5245.9
Table 1: The cumulative regret of 10000 rounds MovieLens with different input dimensions.
A.6 ABLATION STUDY FOR NETWORK LAYERS
We run the experiments on Moviel Lens and Yelp datasets with the different number of layers neural networks and report the results follows. Meta-Ban achieves the best performance in the most of cases. In this paper, we try to propose generic framework to combine meta-lcarning and bandits with the neural network approximation. Since the UCB Meta-Ban only depends on the gradient, the neural network can be easily replaced by other different structures.
NeuUCB-ONE NeuUCB-IND
Meta-Ban
layers 4 layers
4939
7491
4673
5017
7603
4498
8 layers
5033
7764
4796
10 layers
5008
7797
4824
Table The cumulative regret of 10000 rounds on MovieLens with the different number of layers.
NeuUCB-ONE
NeuUCB-IND
Meta-Ban
2 layers
7683
8351
7587
layers
7603
8386
7767
8 layers
7764
8366
7604
10 layers
7797
8373
7541
Table The cumulative regret of 10000 rounds on Yelp with the different number of layers.
16

---

Under review as a conference paper at ICLR 2023
B PROOF OF THEOREM 4.2
Theorem B.1 (Theorem restated), Given the number of rounds T, assume that each user is
uniformly served and set T T Vt [T]. For any & E (0, 0 < s O < 6 S
1, x>>> suppose m, M1, 72, J1, J2 satisfy
Ω max poly(T, L,,p,,,),,))..) e, }), 111 =
P (oly(TT, L). -m
Vnp
vpc2
J1 (poty(T, L)
72 min
log
(6)
L'm2m
p²
E1
(O log m) E2 L2
" Am (O log m E2)
J2 = max +
VTEP
P62
Then, with probability at least
6, Algorithms
has the following regret upper bound:
R & 22/ VVET +0 (LVT) + (1 (1 + +0 3 L+) + Zr
where
T "L PVm
n 10g
11/6 m p/1
ST 00
2n
c2 logg m) O log" m tt2)p 1/2
BT
(pVTTi
L log 11/6
LT
2T =0
+ T(I log m.3t +0
log
pm2
Pvm
LATS
+0
log log4/3 m
p2/3m2/3
With the proper choice of m, we have
Ry O(VT) (VT+LVT+ 2T log(T/8) + O(1.
Proof Overview. Different from existing works Zhou et al. 2020 Zhang et al. 202 that bound the regret of one round by kernel regression in Neural Tangent Kernel, directly upper bound the mean of regret of overall T rounds by building martingale difference sequence with respect to ht First, we decompose the regret T rounds into three key terms (Eq. (9)). where the first term is the етrоr induced by user learner 0* the second term is the distance between user learner and meta learner, and the third term the error induced by the meta learner θ
Then, Lemma provides upper bound for the first term. Lemma E.2 is an extension of Lemma E.3 which is key to remove input dimension. Lemma E.3 has three terms with the complexity training error induced by a class of functions around initialization, the second term is the price of choose the function class, and the third term is confidence interval induced by concentration incquality for ("). Lemma C.1 bounds the distance between user learner and meta learner. As this bound has the term ( / m.). this bound can be reduce to vT
(VVT), where the first term
with proper choice of m. Lemma bounds the error induced by the meta learner using triangle inequality bridged by the user learner.
Bounding the three terms in Eq. ( completes the proof.
17

---

Under review as a conference paper at ICLR 2023
Proof. Let x = arg m hus (X5.,) given X,, Me, and let O be corresponding parameters
trained by Algorithm 2 based on N1 (x]). Then, for the regret of one round E [T], we have
Rg ut
E
Irī uel
E
[r f(x;; 0--11 + (xx)0(x;1]) ri]
E
('2 [(x]: 011) 1 (xx; f(x;; 0,) (x) + ((x;;6)) MT (xx) rz
I E r71x;
1r/ - 0;1)) + + |5xx 0-0)) f(x;: [(7x
+ E (xx))00) N1th (x,) rr nix;
(8)
where the expectation is taken over Ti conditioned x,,; for each i [A]]. 6--1"" are intermediate user parameters introduced in Lemma E.4 trained on Bayes-optimal pairs by Algorithm 3 e.g..
1x--1-ri-1). 1). and O2 are meta parameters trained on the group N,*((x))) (x7) using Algorithm Then, the cumulative regret of T rounds can be upper bounded by
R
Rg Uu
T
T
T
E
[lr - f(x7; 0-:)))1
+
Σ
-(2;; + f(x;: -
Σ
[(()) (x;) T
r2
[=1
1=1
(0)
Σ
Venu + (LVHI)) + (1 {1) (2)) log(T/6)
NEN
Σ
Be |1)(x;;; 0,) - "xx]]x'xx))>) "0: + Z
Σ E
f(x);07) 1,0, (xx) re
rs
t=1
VEIuf + (LV + +1++ (22))22pppp 2n log (T
N
T
T
13e . (x: θ.) g(x;; 01 + 2g| + Σ
[f(x): (1) I N.t (xx) - rd)
+
rxlxe
18

---

Under review as a conference paper at ICLR 2023
where (a) is the applications of Lemma E.2 and Lemma C.1 and (b) is due to the selection criterion of Algorithm where 8% = 0% according to our initialization. Thus, we have
RT
Re
V sin + (Iv/44) + (1 + (1+5)) (og(T/6)
WEN
T
[B (1x(xx;;x) - 9(1;; 00)ll2 Zz]
Σ
E ri/xe
[[xx; O.) 0.)
(xx) f(xii 01=1) + fxx1; r3
V 11 + + (LV (1+ E1) log(T/8)
WEN
T
+
13. (x-111(x;;00) - 9(x;; 0o)lle + Zzl
Σ
[[(x; O₂) (x)) s(xii 0th + Σ E
1x -r
r1
2
Σ
V VELLo7 + +0 (LVV + (1+ (1) 24 log (T/6)
NEN
T
+
[B: : [1g(x(; θ₂) - g(x:: 20) 1|2 + Zz]
1=1
(d) $ 2
VETT+ + (LVT) + (1+ E1)
2T log
+
3. (x;; Ox) 9(2;; 0o)lle
Ze
f2
where (c) is an application Lemma E. and Lemma C.1 and (d) is an application of Lemma E. with dteffding-Azuma inequality.
For I, recall that 3r O'2²r'' Vea log' -(t" log" m m=te2)p An Then, using Theorem Zhu et al. 2019), we have
Allen-
O(pymez)
T
Σ 3 o (Vlogms)" L' 0ollla) s o (T ( log m,343311 L2) S 0(1)
I
(10)
Ea
where
E2 is the Lemma E.10 and Eg is because of the choice of m (8, has the complexity of
O m1/z)) and ((730)).
19

---

Under review as a conference paper at ICLR 2023
For 12, recall that Ze = 0 [[-1)] 1o/11//
+ (L+1)2/m log 3//3 +0 (I
(iw-) pvm
log m
pmn pm.//6 1/6
I (t-1))
1/3
+ O(LB) +
log m
Then, we have
Pvm
T,2 log 11/6 m
LT Ppm
1 50
+ + Vm log m
+0
log m
pm 1/6
L
(11)
+ +0
/4/3m223 log
log 4/3
=Vr.
12 has the complexity Ö ( Therefore, /2 S O(1) when m 2 $)(T.0).
For 13, the choice of m, have (1+ S (().. The proof is complete.
C BRIDGE META-LEARNER AND USER-LEARNER
<2 1, O, suppose m, m, T2. J1, J2 Lemma C.I. For any E (0.1). 1). 0(,)), E2
satisfy the conditions in Eq. Then, with probability least 1- 5, for any E [T] and x, satisfying
||xe||2 = 1, given the serving user u E and O returned by Algorithm 2 based on Ny (xt), it holds uniformly for Algorithms that
[8(x; f(x;; 0,) < B 19((x; θ2) - 08)122 + Zr,
(12)
where
3. O 62 log m)
log2 m 2/2
Opp/mez)
(t- (t-1)) log 11/6
Z, =0
(L+ 1)2
m log m.3
/61
0 (1((t-1))
log m ))
(
Pvm
Proof. First, we have
((xx;01)) f(x:: 0,) < fi (x;; 0- (g(x;; 0 1),1),0 0:0 0K) f f(x;; 08)
(13)
(g(xs; 0211).00- 0%) + f(xi; (N) - f (xri O,
where the inequality using Triangle inequality. For 4, based Lemma E.9 we have
1 log 11/6 m
log
I < O3w2/313 mloomm)))lmm [ 1/ < 0
pmn1/6
(n) 1)² pvm
where the second equality based on the Lemma E.8 (4): |00y1
08ll2 l22 -
log m
(t-1)² Pv/m
log m = w.
20

---

Under review as a conference paper at ICLR 2023
For 12, we have
[g(xe (0-1): 00-1 - 06) + f(x;;;) - f(xx:
(x(e 070 1), 00-- 0%) (g(x;; 0.), 0, Aull
+ (x0x;;; Oe), Or Oa) + f(x;; (8) f(x(: 0x)l
(0(Xe 0i-1); 07-1 08) (x(x;; 08), , Ob0
(14)
+ (x(x; 08), 02 Oo) (g(x: θ,) O: Oo0
+ [0(x;; Ot), 0r 0n) + s(x1; 06) - 1(x1:
where Ei, E2 use Triangle inequality. For Iz, have
(g(x;;; 07-1): 0 0%) (g(x;; (i), θ Oa)
(g(,;; 0/- 6-h 0%) (0(x;: 06), 0-- 06)1 + (xx;;; 00), 0-- -0) (x(x;; 0%) O. -b03
(g((;;; 1)-1) g(x;; 0% ll2 110"-1 8 + [1g(x; lle
100
0% - (θ, 00)112
M1
M2
(15)
For M1, we have
(t 1)3
M1
0
log m
[1g((x;; 00-1) 9xx;;
Pvm
(16)
(t- 1)3 Pvm
4/3
O
L*
log m
Es
where E3 is the application of Lemma For M2, we have
E.8 and Es utilizes Theorem 5 in Allen-Zhu et al.
2019 with
Lemma E.8
Oo)ll (100) 0% (0: 00)ll2) 11
(11)(x;;
0o)ll (100= - 0 la + 10: 0oll2) 1)3
(17)
O(L)
0
(1
log m + Be
Pvm
F6
where Fs use Lemma
E.
E.8
and D.1
Combining Eq.(16 and Eq. C we have
(6))
1 000 Lt
(t 1)3
1/3
+ +0(1
(1((1) Pv/
(t (t- 1)3
log m )) +(L3).
log m
(18)
Pvm
For 14, we have
11 = (g((x Qo), O Qo) (x(x; θ2), θ 9o0
< (g( θ2) - g(x:: θn) 1/ | Oollz
(19)
<3 (1 O.) ( 0b)
where the first inequality is because of Cauchy- inequality and the last inequality is by Lemma For Is. we have
Is (x Oz), O 1o) + fx;; Op) - f(x:: 0.) (L 1)² m log l
(20)
where this inequality uses Lemma D.2 with Lemma D.I Combing Eq
8
and 20 completes the proof.
Lemma C.2. For any E 1) e (o, (0,0 < é S E2 & 1, > O, suppose m, mh 12. J1. J2 satisfy the conditions in Eq. ( Then, with probability at least 8 over the random initialization,
21

---

Under review as a conference paper at ICLR 2023
after t rounds, the envor induced by meta-learner is upper bounded by:
E [x (p) -rell we]
Ne
(21)
O (11 0₂) g(xx; 86 )l1))
[
L
log(t//)
Σ
+
Vt
22
WEN
where the expectation taken over Tt conditioned on Zt.
Proof.
E [x) - rrallue]
xe
Σ E [I((x;;))) ((xx;001 + (xx: 0/-11) - rell [e ne
(22)
[fx; 01) - 022;1111111 Σ
E Te
[x,; rel 41
For 11, applying Lemma C.1 with probability least 1 8, for any | ll2 1, we have
T
T
(llg(x;; O₂) - g(xe; )112)
I $ Σ (3: (x θ.) - ((xx666)11 + Zz)
(23)
Vt
where E1 the result of choice of m (m 2 2T for 3r and Zz.
For I2, based on the Lemma
E.1 with probability at least 1 5, for any E (0, 1], we have
12 S Σ
VEIu + +0 (LV 14
+1+ 2nr log(t/0)
NEN
(24)
[++1
2lg((t/6)
Hi
O
+
v
wEN
The proof is complete.
D ANALYSIS FOR META-LEARNER
Lemma D.I. Given any E (0, < < 5 5 0, E (0, (0,0()), suppose
m. Th n2, J1, J2 satisfy the conditions in Eq. and Oo 03 randomly initialized Yu N. Then, with probability at least 1 8, these hold for Algorithums 1
1. Given any A C N, define Lx((),)) = 2
Σ
(f(x; - -r) where Or, is re-
KEN
(x,))ETT)
turned by Algorithm given N. Then, we have (Or() S f2 in Jo rounds.
2. For any j E [J2], ||0 - O s O(n't' /es log² +01? log" m m- An 3
Olpymez)
Proof. Define the sign matrix
11 if 0f 0;
sign(0pp)
(25)
--1 PN
22

---

Under review as a conference paper at ICLR 2023
where B]] is the i-th element in A.
For the brevity, we use 8. to denote Mig For each u E N, we have T Given a group N, then recall that
A
LN=
Σ
c 0
100/112-
m
WEN
Then, in round for any j E [J2] we have
U (-1) = 1/2 V (0r)uex LN
(26)
Σ
Σ sign(0 (+)
1)2
m
mEN
wEN
According to Theorem 4 in (Allen-Zhu et al. 2019), given ) O (1-1), we have
()) 5Cm(06-1) (Ve ( - (-11))
V(LN(00-1) 13 /m mm - ((( --111
(N((0-11)) -72l
Vo
C+
Σ
(ign(0)))l21) Vey- Carll+
Vm
E1
BEN
WEN
= 1/3 1/3 L ttm ml m
(g )|la (x((
0
nEN
ueN
- =1)O(LL'm)I
Vg C
sign (
REN
MEN
(27)
= (v((6)) S (x(00-1) 72
VV f1122|1 fxrl2+
ueN
+ n2w0 1/3 /2 22 tog m
1 C22 (g(()) (t)mmm))
Σ
11 Cl2
BEN
neA
Ve Cxlll + n2w 13n22 /ll.gmmm + 2
(28)
+ (x(())) S (L)(OU-))) - Σ pm
(N(()))(()-)))))))))))))))))))))
tua
NeN
R
+/2202133 1. homn/tpnllae log
L(08) + Σ C(0))
neN
T2 V (Nv(O + m/ 1/3 llg (oolg////v(llo)))+--00 +
(29)
where E, is because of Cauchy-Sehwarz Schwarz inequality inequality, Eg is due Theorem 3 in (Allen-Zh et al. 2019 i.e., the gradient lower bound. Recall that
Vnp
VPe2
) LN((O) Ottlog² m)
1/2 min θ
LLL2
L222n2
(30)
("(((oo m) 62)
L
1+3 X m 62))
J3 = max
TRE2p
pE2
23

---

Under review as a conference paper at ICLR 2023
Before achieving G)) c2. we have, for each u E N. ((O)) = (x(O ()),foo for 1,, we have
4 S - 72
Σ V
pm
[(0))x(())1)))++
WEN
+ m2 13 L m ton m
Σ ((0))))
neN
REN
-- /mmm
(x()))))))))))
22
REN
(1201/3 1 m tpn m + 112t21.2
Σ v [(())))(
+
REN
/ Σ
(=(::)
O
Es
qan /pm
Σ ((;)
12
REN
(31)
where Fig is because of the choice of 112- As Lx(( S O (1log m), we have (0)( S 62 in Je rounds. For 12, we have
n2VUP
12
S
Vcz /
t
F6
12XVP
V + n2w 13 nT? log O |
t.
En
(32)
VCz + m/ 1/3 V my Ot m) + 022
t
112 pE2
)
where Es is by ()-)) 2 e2 and (x(O0)-))) S (o)(O E7 is because of the choice of 1/2-
Es is according to Eq. 30 and
Combining above inequalities together, have
(r)( SLN(0G-1)) - o 12n/npm
L(O:)) O 722 pP2 )
Σ
1
nEN
(33)
<LN(0G-1)) O P22/p22 )
Thus, because of the choice of J2, 172 we have
1/ 72 pEZ )
(x(()),)) < (r) J2- 0
(34)
12 pea
< Ol m) - J2 θ
- 62-
t.
The proof of (1) is completed.
According to Lemma E.8 For any j E [Jı], C(O))) < (1 21
ppm
1( (1))) Therefore, for any
dupp
E [n)], we have
(44))
((0:) < Σ v /C(0%) 5
((8%))
mmpm
(35)
(2:)2
<
O(V 1o log? m).
pm
24

---

Under review as a conference paper at ICLR 2023
where the last inequality is because of Lemma
E.8 (3).
Second, we have
J2 (0()) (1-1))12
(J.)) 0ulla -
j=1
J2
A
1/2
7p L
Σ
sign (8) ||
m
(36)
5=1
BEN
uEN
An
1/
Cll
m
j=1
MEN
For 13, we have
Σ r2ll
Σ
V0r
Σ
1/2 W
Σ
1V Cl12
uEN
1=1
NEN
J2
12 n
1 p Cll
(37)
Fig.
J=1
KEN
(12) Vntm
v 1(O))
Eg
Σ NEN
Vz 2
( ntm
((0%)
1=1
E10
uEN 1=1
(nit² 11
(olm))n (11)) - n- O
OOV 1 log2mm) m)
(38)
En
3/22/225/22 V tlgg m
<
0
MPPvm
where E₁ is because of [W| S n, Eg is due to Theorem AAlen Zhu al. 2019), and E3 as
the result of Eq. (35)
Combining Eq. 36 and Eq. 38
we have
O0 m223/2233 Vlog" + pan
[10
T.Pym
3/23/213 Vl0g"" O O12logg" m Le2) ppAn
<0
ThPyme
(39)
O On2t3 V Vog m) + (t log" t22)
O(p/mez)
=Br.
The proof is completed.
D.I ANCILLARY LEMMAS
Lemma D.2 WWang et al. 2020a)). Suppose m satisfies the condition2 in Eq. if
Q(m 3/2 r, 3/2 [oo [ogg(Tk12//033/3)) < O(T + -
25

---

Under review as a conference paper at ICLR 2023
then with probability at least 1 8, for all θ, O' satisfying |00 Oul2 and ||'' Ooll2 S
X E R. ||x|| 1. we have
[f +) f(x; - (Vef O' -11 O( 1)² m logm).
Lemma D.3. With probability at least 8, set 1/2 O Fz.m ) for any O' IRP satisfying
|| - Opl12 S 81 such that
3Lv1 v2
Σ 01) - rr Σ ffx+; 0') - +
Proof. Then, the proof is a direct application Lemma 4.3 in (Cao and Gu 2019) by setting the loss as L. (6,) (s(x;; θ.) - rr,,, R = B1 Sim
LR and v = 17. V2vt'
E ANALYSIS FOR USER-LEARNER
Lemma E.1. For any (0, 1).1).0 < P O suppose E1 S and m, Th J1 satisfy the conditions in (o After T rounds, with probability 1 1 5 over the random initialization, the cumulative error induced by the user-learners upper bounded by
1
E Tx
ral T Mel
T
LR + O(L E
(T/(
Svn
+
T
T
where the expectation is taken over ri conditioned on x and T, is the historical data of u up to round
Proof. Applying Lemma
E.3 over all users, we have
E [If(xx; 0
rel
TT uc]
ri/xe
Σ
E 11f(x-;0%_1) - - 1.
T
Ke
(40)
uE N (X,STYJETT
Σ
E1 + + ( + +1 +1 & 2n log(T/5)
T
NEN
where applied the union bound to over all users and Even ni = T. Then, given a user u, then, nu = - 1( u} where 1 (( = -u} is the indicator function. Then, applying Hoeffding-Azunn Azuma inequality on the sequence /4 Vu E N, we have
get (og(T/5) because of
Σ
MT
E
2n log(1/8)
KEN
uEN
=VTT + / l/glog)
Then, by simplification, we have
1
E
[xf(x;; 1 rel T, uel
T
(41)
L
2 2log(T/6)
S
V
+
0
/T
+ +11 + E
T
The proof is complete.
26

---

Under review as a conference paper at ICLR 2023
Lemma E.2. For any ò (0, p S O suppose 0 61 S and m, m, J1 satisfy the conditions in Eq. In round E [T]. given u E N. let
x = arg max X
hu (x1,))
the Bayes-optings arm for u and rē is the corresponding reward. Then, with probability at least 1 ó over the random initialization, after T rounds, with probability 1 5 over the random initialization, the cumulative error induced by the user-learners is upper bounded by:
r21 TT-1 up]
V + VT
L
2log(T/0) T
(
where the expectation is taken over ri conditioned on x Te {(x,, r.) : ut = E [1) stored Bayes-optimal pairs up round for u, and 0 are the parameters trained T
according to Algorithu 3 in round t 1.
Proof. Based on Lemma
we have
T
E [II(x|;
- rill T we]
T
Σ
Σ
E
11(((x;;; 01 rzl T
(42)
NEN (x;,r;)T,,"
Σ
V Vapg + +0 (IVIt) + (1 E 24 log (T/5)
T
where we applied the union bound to å over all n users and so we get log(T/6) because of ELEn pz T. Then, given a user u, then, μuj- = L(u u} where 1f u} is the indicator function. Then, applying Hoeffding-Anin Azuma inequality on the sequence / Vu E N, we have
Σ MEN
E
2n log(1/8)
NEN
=VnT
22 log(11/)
Then, we have
T
[If 0:: - r77l T wel
T
rilx;
(43)
61 T
(1)
[
L
2log(T/8) T
Snn
+
+ 011 + =vI
V
VT)
The proof is complete.
Lemma E.3. For any E (0,1).0 < I O(2). suppose O < 61 S and m. Th J1 satisfy the conditions in Eq. Eq. In round where N serving user, let xe be the arm selected by some fixed policy ny and rr is the corresponding received reward. Then, with probability at least 1 - over the randomness of initialization, after [T] rounds, the cumulative regret induced by is upper bounded by:
1
Σ
E [[f(x;00 00=:000-)) TTl 1T,
r- (x+rr=)TT))
C1 S
+0
3L
+ +(1+
2 2log(1 18)
22p
where the expectation taken over r, conditioned on x, and Ti" = (xx,, r+) u, = u. [t]] is the historical data of u up to round
27

---

Under review as a conference paper at ICLR 2023
Proof. According to Lemma E.5 with probability at least - 6, given any |||||2 1, s for any round 7 in which u is the serving user, we have
(1x: -1 -( +.
Here, we will apply the union bound of over all j rounds, make this bound hold for every round of u. Then, in round where u is the serving user, let be the arm selected by some fixed policy Ty and ry is the corresponding reward. Then, we define
V
E [1f(x,; r-ll 1f(x 07-1) rrls r-|x-
(44)
where the expectation is taken over r, conditioned on x,. Then, we have
[[]
E r, X
[1 07-1) rr]] [x+ 07-1)
F =
where F., denotes the o-algebra generated by T Thus, we have the following form:
Σ
Σ
E rx
[x
07-1) r
Σ
1[(x;00=1) Trl.
(xT,)T)ET
(XT.
(x.,
(45)
Because Vi,..., Vi is the martingale difference sequence, applying Hoeffding-AAzur inequality over Vi...., Vpp. we have
Σ
E 1r/x7
[1f((x;;; 07-1) r+1 Tr,
pe (X+,T+)ET
2 log(110)
(46)
S
Σ
- =2))
Pi
(XTTT
For I,, for any Ō satisfying
100 08112 s 0
(M
log m
we have
Pv/m
(0)
3L
Σ
rr 1f(x;;0"-11
Σ
-
14
(x-J+)ETT
(x-J+)ETT
3I.
Σ (f(x;:0) r2)3 +0 +
V c4
2
(47)
(x..F))ET
261
3L
+
O
V
where is because of Lemma E.6 and I3 is the direct application of Lemma E.8 E.8 (2): there exists
satisfying 10 11 S
o (x))
log such that 1 Ine (f(x;; 0) r,, )² s E1.
Pym
Combing Eq 46 and Eq.44) (4)) have
Σ
E [1(();;;1]) - rzl 1 Tr, u| lx,
S
2E1 uit
+ +0
3L /2
+ (1 + 1
2 log(118)
(K,
(48)
Then, applying the union bound over ó, for any E [ki], E [44').
Based on Lemma E.8 (4), for any 0z T E [t], we have و:ل - 0 ll - O
[1t') pym
log m
Thus,
(xZ)²
holds that ||0
0% ll <
pvm log m
Then, apply the union bound of over all na rounds. The proof is completed.
28

---

Under review as a conference paper at ICLR 2023
Lemma E.4. For any ò (0,1).0 p O+)) suppose 0 c S and m, m, J1 satisfy the conditions in Eq. In a round T where u E is the serving user, let 2 be the arm selected according Bayes-optimal policy x²:
arg max (xr,)) xx.
and r² is the corresponding reward. Then, with probability at least 1 8 over the randomness of initialization, after E [T] rounds, the cumulative regret induced by with policy x² is upper bounded by:
Σ
E r7/x
(x
- r ,,,
17
(x),))))T,
2E1
+0
(
3L
+1 +(++
2 2log(u0/00 /0)
bg 12
where the expectation is taken over r conditioned x Te" ((x+,++) u, =, {t}
are stored Bayes-optimal pairs up to round t for u, and 0=-², are the parameters trained on T
according Algorithm 3 in round T 1.
Proof. This proof is analogous to Lemma
E.3 In round 7 where u is the serving user, we define
V
E
r1 - [x] (x(x;; rfl-
(49)
x
where the expectation is taken over r conditioned on x Then, we have
[[, E [1xxx;0;;1) Tr,, (II[(x;; - r. [.]
r:|x;
Therefore, .,,... Vig is the martingale difference sequence. Then, following the same procedure of Lemma B.3
we can derive
Σ
E
- rf u]
17
2c
3L
2 2log(1/5)
SV
+
O
(1 +1+
12
Based on Lemma E.8 (4), for any 0: T E [t], have 110 -0% O
(1x)²* Pvm
log m)
Thus,
holds that |0-.- 0% ll S O (M')²
log m
Pvm
E. ANCILLARY LEMMAS
Lemma E.5. Suppose m, mıs 7n satisfy the conditions Eq. any x with ||x||2 = and E (T), N, it holds that
(6) With probability at least for
(f"nllog m
tnnL log 11/6 m
1f(x; 22+0
P/m
Ec- )+
+
p/1
29

---

Under review as a conference paper at ICLR 2023
Proof. This is an application of Lemma C.3 in (Ban et al. 2021b). Let Ou be randomly initialized.
Then applying Lemma E.9 for any ||x||2 1 and 1000 0ol - w, we have
(x(x; - [xx 0o) + (Vo. (x,; 00). 0: 0o>l + O mmlogm)))10 fo foll2w
2/3
I1
Boll2 +01, / m log(m)) S 22 + || 0o)
10r 0 80ll2 1/3
Is
1 PVm
4/3
(50)
2 52+0(L) o
log m +0 122 m log(m))
O
log m
PVm
13
( L PVm
LL log 1/66 m pmnt/6
2
+0
where I is application of Lemma 7.3 in (Allen-Zhu al. 2019). La is by Lemma E. (1) and Lemma E.8 (4), and I3. is due to Lemma E.8 (4).
Lemma E.6. For any 5 E (0, 1), suppose m satisfy the conditions in Eq. 6 and v O //²)).
Then, with probability at least 1 8, set mn 0 22upm) for algorithm 1 3 for any 0 satisfying
|10 0% ll S O (w-))* pym
log logm) m) such that
27
Σ 1f(x;;0"_)) rrl S Σ (( -r -
33V v2
(51)
Proof. This is a direct application of Lemma 4.3 in (Cao and Gu (..(0% (x+:00+-))) rrl. and R (x")²² log m,
2019) by setting the loss as
L. and v R2, where // is v 22n2
P
some small enough absolute constant. Then, for any 0 satisfying there exist small enough absolute constant v/, such that
10 0 2 < o (ار) Aym
log m
Σ
( <
L. (+) 3/
(52)
T=1
Then, replacing e completes the proof.
Lemma E.7 (Lemma C.2 (Ban et al.
2021b)). For any 8 E (0, p E (0, ((+)), suppose the
conditions in Theorem 4.2 are satisfied. Then, with probability at least 6, in each round E [T].
for any ||x||2 1, 0,-,, 0/ satisfying 110%- 0% I O (uz'² ppmm
log m and ||09 8 l|l S
(1 Pv/m log logm) m)) we have
(1)
(x; 01-11) - f(x; 0--
)) /1/3mm216 (f
L1L3 log 5/6 m
Lt
log m) +
1t2L2
log 11/6
x o
o
(53)
Pvm
p//3m=/6
=Ge
tL log" m )) O(L). ))O().
(2)l fix 0x:00_ <
1+
(54)
p2/3m 1/6
Lemma E.8 (Theorem I in (Allen-Zhu et al.
2019)). For any O < < $1,00 S O(/L). Given
user u. the collected data {xr, xxr,,
suppose m, mi J1 satisfy the conditions in Eq. Define
f. (0") E( (f(x; 0²) r)2 Then with probability least 1 - 5, these hold that:
30

---

Under review as a conference paper at ICLR 2023
1. For any j E [J], ((0))) - -1-
()
Mr
2. [(0(i) ) - (1 in J1 = publl log(1/cL) rounds.
3. [(0%) - Oμr log" m).
m).
4. For any j E [J]. 10 - - - O
(mz)* Py/m
log m)
Lemma E.9 (Lemma 4.1, (Cao and Gu 2019)). Suppose Om (m/23 1/22 (To (6)]3/2) S
w Σ OL 6 [log m] - Then, with probability at least 1 - over randomness of 8, for any t e [T] 2 = 1, and 0, satisfying |00 Poll S and 110' 0oll I w. it holds uniformly that
If(x:) f(x; 8 (Vo ). 8¹) = O(w / m log(m)) 10-1222-
Lemma E.10. For any 8 (0, 1), suppose m, mh J1 satisfy the conditions in Eq.(6) and Og are randomly initialized. Then, with probability at least 6, for any ||x|| = these hold that
1. fxx; 00)ll2 I OLL),
2. [x; 8b)1 =
Proof. For (2), based on Lemma 7.1 in (Allen-Zhu et al. 2019), we have (f(x; S 2. Denote by D the ReLU function. For any / [L].
f(x: Bo)ll S l| D ... D1ill [D (11 xx S (((V))
where the inequality is according to Lemma 7.2 in (Allen-Zhu al. 2019). Therefore, we have
a/ (x; 0o) I O(L).
F RELATIVE GROUP GUARANTEE
In this section, provide relative group guarantee with the expectation taken over all past selected arms. For u, u' E N u F u', we define
E <x>xx
(x+))=) {u, u'
E
E 0- 11l
[[(x=
0--101 V y
(55)
x TT
and
E X
[w,(x))] = (u,u'
IE
[
[E(r>|u[]] x
(56)
X
where (x+) ) the detected group and (x+) the ground-truth group. Then, we provide following lemma.
Lemma F.1 (Lemma 4.6 Restated), Assume the groups N satisfy 7-gap (Definition 2.2) and the
conditions of Theorem 4.2 are satisfied. For any (0, 1), > 1, with probability at least 1 - over the random initialization, there exist constants Ci C2 such that when
n64v2 + &22 (log (1+E0) + 91 9 +2
log
401 4[++.))
=T.
72(1 /3n log(n/6))
given a user u E N, it holds uniformly for Algorithms 7 that
E [u((x) C N.
and TT
E
= (xxx))), ).. 2
where x, is uniformly drawn from Th" x and Ti = (x, :4 WAAEEE [+] is all the historical selected arms when serving up round t. Recall that
tL3 log 5/6 m ))
Lta
+ log 11/ m
G. = 1 1+0
O
log
+ 0
p//3m116
Pvm
p4/3m
t log
t log
11/6 m
&, = 2+0
+
pvm
pm.
31

---

Under review as a conference paper at ICLR 2023
Proof. Given two user u, u' N and arm X,, let rr be the reward generated on x,, and r4 be the reward u' generated on X,. Then, in round E [T], we have
[|,,
- + x,]
X
x
Σ
E 1|r r x-]
Test
X+
1
Σ
E I|r - f(x+; 01) + fxx+; f(x+;0 f(x;; 0/L11 -rrl x,]
H4
1
1
Σ
E [|+ f(x,;:0-11)
Σ
[[f(xx; fxx;;
Tr/xr
1i x-E7?"x
X+
+
Σ
E +
(1f(x;;0) -
(57)
where the expectation is taken over Tr, r conditioned on x,, According to Lemma E.3 and Corollary respectively, for each u E N, we have
Σ
E I|+ /r(x,
f(x;; 0 1111 u).
14
2e1
V2 (V2r1)
3L
) +11 (1+)))
2 2log(u 18)
O
14
(58)
Σ
[1f(x,; -r'111 24
14
ry xx
XrET
Xr
2e1
3L
2 2log(17 /8)
O
+ +11+ +1++
+ Ce-
V242
Due to the setting of Algorithm I | 07110 ) - f(x;; 04-1) S eoly for any u, w' Nu. (x+).
given X, E | x. Therefore, we have
E x T xx [rrrrt
E
||,
++1
x-1
(59)
2c
3L
2log(u 15)
+2
(
22
+11+50)
+
14
+ Ge
Next, we need to lower bound as the following:
201
3Te
+ +11+ +1)
21og(1/8)
+ S ?
22
14
2v
(
26
3Le
+
+(1+ Vo)
2 2log(n /8)
+
S 72
(60)
22
4
2
26
3Le
2
21og(u8/8) 147t
12
4
+
+
(1+
(G))
S
22p
4
By simple calculations, we have
2
2 + 4el + +22
γ 14
log 2r <
+ log
(61)
32 (1 + E
4(1 E,
Then, based on Lemme 8.1 in (Ban and He
2021), we have
14 > 64 (1 + E
22,² (1
9L2cp + 461 + 2C?
72 log
llo
(62)
72
4(1 + +.)2
32

---

Under review as a conference paper at ICLR 2023
Given the binomially distributed random variables, 21, .2...... Ft, where for T [8],2, 1 with probability 1/n and 27 with probability - 1/n. Then, we have
t 7
Mi 2r and Bluy]
(63)
Then, apply Chernoff Bounds on the n4 with probability least 1 8, for each a N, we have
1r 1 1 + 3n log(n/))
nyp
=t +
(64)
3n (n/0)
Combining Eq. 62
and Eq.644 we have: When
n64 Ec) llo
32+ o
log
72
4[1+5.)²
tz
72 + /3 log(n/8))
it holds uniformly that:
2 { 2El
3L
2 2log(t/8)
)²)=3 = 2
2
( 1e
+
22
+ +1+ V
s
This indicates for any u, E and satisfying [x 03-10 f(x;; f(xr:0<-1)) :) S 2 ie., u (x,), have
E T
E 1rrnt
[|r
r/l xx1 S7.
(65)
This implies
Na (x,, S (x+,))
x
For any u, u' E (N(x)),, we have
E
E [r, r x-1 (rottt
X- T. be
E [r, f(x+; 0;-1)) lx,
Σ
[f(x+i0ū_1) - f(x;;
14
1i x-
ET
E (f)x |e]
+
X,ET.4
x
-0
Thus, when t T. have
E
f(x;;
XT~Ti'l |x
Σ
I|r, s(x+;
Σ 1x((x=00())) w']
14
rr|x,
14 x,
x
ET.
ET." x
x2
Because < 1-11 when 2 Thus, we have
E
[1f(x+;0%11) -f (xxx;=0"') S v-1
x, ~
Therefore, by induction, this is enough to show
E
Wi = =N((x,)) when and t T.
X, x
The proof is completed.
Corollary F22. For any E (0, p e (0, 0(+), suppose < E1 S 1 and m, J4 satisfy the conditions in Eq. (0) In each round & [T], given E N, let (xt,g) rt.j) ) be pair produced by some
33

---

Under review as a conference paper at ICLR 2023
policy Tj. Then, with probability at least 1 ô over the random initialization, for the user-learner 8--1 we have
Σ
E Nr5
[Irr - f( 07-101 Jjz
Pi
(raaira))TT
26
3L
2log(pi /8)
+
+ +1+ (1)
Ses
2211
14
where T2 = {i
xx uy u, [8] is the historical data according to n the rounds
where u is the serving
Proof. By the application of Lemma
E.4 there exists 0-
satisfying 1 0 ll2
O (w() Pvm log m) trained on T ( following Algorithm
Then, similar Lemma
E.2 we have
Σ
E [Ires sxx,, (0 02-1)1
11
Σ
E Pralxta
rras f(x 0-
(rrg (ETT)1,
(66)
Σ
[f 0 f(xe.j) 1111)
Pi
(
2E1
3L O
(log(O(4*k)00))
(1+
+ Sr.
12
1
where I is an application of Lemma
E.4 and Iz is because of E.7
The proof is complete.
34


Reviews:
[{"review_id": "ZRBhf7DRyT", "reviewer": "Reviewer_Uhmg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper considers the problem of online collaborative filtering. In each round of this problem, a user is randomly sampled and a set of items/arms are provided to the learner. The goal of the learner is to recommend one of these items to the user so that the cumulative reward it collects over time is maximized. One key structure that is usually imposed on this problem is the cluster structure: for each item, it is assumed that the users can be grouped into a small number of clusters, where users within the same cluster have the same reward for the item. This problem has received significant attention in recent years. Previous works assumed that the reward of each user-item pair is a linear function of the item vector [1]. The current paper extends this to consider more general non-linear reward functions. In particular, the paper uses neural networks to model the unknown reward function. The authors provide a meta learning based algorithm (meta-ban) that achieves O(sqrt{nT}) regret for this problem, where n is the number of users and T is the number of online rounds. Experimentally, the authors show that the proposed technique achieves better regret than baselines on benchmark tasks. \n\n[1] Li, Shuai, Alexandros Karatzoglou, and Claudio Gentile. \"Collaborative filtering bandits.\" In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pp. 539-548. 2016.", "summary_of_the_review": "While the problem being studied is interesting, the clarity in the paper needs to be significantly improved. And there are several concerns with the theoretical and experimental results presented in the paper. I'd appreciate if the authors address my comments above.", "strength_and_weaknesses": "Strengths:\nThe problem considered in the paper is a nice generalization of the past work to non-linear rewards, and is relevant in practice. Some of the theoretical results in the paper (e.g., regret bounds not depending on dimension, no distributional assumptions on the arms) are interesting, but unfortunately lack a thorough discussion on how these were obtained.\n\nWeaknesses:\nI believe the paper is a little bit under-cooked. The clarity and presentation in the paper can be significantly improved. The algorithm is not well motivated and described. The theoretical results are not well discussed and the proofs in the appendix could be presented better. Here are some key concerns I have:\n\n* Clarity: I had to take multiple passes through the paper to clearly understand the notation, the main algorithm, and the theoretical results. \n  - first of all, the algorithm needs to be clearly explained. what is the motivation behind introducing a meta learner in Algorithm 2? It is never mentioned.  What happens if we solve the objective in Algorithm 2 exactly (i.e., increase $J_2$ and don't warm-start $\\Theta_{(0)}$ with $\\Theta_{t-1}$)?  Will the resulting algorithm have poor performance?\n  - why is $\\ell_1$ norm used in Algorithm 2? Why not $\\ell_2$ norm?\n  -  it is not clear how the proposed algorithm is different from the algorithms proposed in prior works such as Li et al. 2016 [1]. Is the extension to nonlinear reward functions straightforward? What are the key challenges and insights needed for this extension? These things were never discussed in the paper.\n  - while Theorem 4.2 is interesting, a proof sketch in the main paper would have helped the reader understand the proof better. Currently, it is very hard to understand the key ideas in the proof. I tried looking at the appendix, it is poorly organized and without a high level overview of the proof, I found it hard to read through the appendix. For example, I tried looking at Theorem B.1. It refers to Lemma E.4, which in turn refers to Lemma E.3, which in turn refers to E.5 and so on. By the time I traced this graph, I lost track of many things. \n  - some key details in the experiment section are missing. For example, details on how the classification datasets are converted into collaborative bandit problem  should be added to the main paper. This will help the reader better understand the task being solved.\n  - there are several issues with the notation. Here are few examples: L in section 3 appeared before it was defined. Operator grad_{theta^u for u in N} in line 8 of algorithm 2 was never defined. \n\n* Theoretical Results: \n  - the regret looks too good to be true. why is there no dependence on $d$? Even in the linear case (without and collaborative filtering stuff), the minimax regret has dependence on dimension. Are there any assumptions that are causing this to happen? In particular, is assumption 4.1 the main reason for these rates? A discussion on this would be appreciated.\n  - On a related note, why is there only a $T^{1/2}$ term in the regret? The NTK kernel is a very complex kernel with slowly decaying eigen spectrum. It's worst case regret bound in standard contextual bandit setting scales as $O(T^{1-d^{-1}})$. Can the authors explain what is causing this discrepancy?\n  - the cluster sizes and the number of clusters never came up in the analysis at all ($q_{t,i}$). Shouldn't the regret depend on these quantities? I'd appreciate if the authors make this dependence more explicit. \n\n* Analysis:\n  -  The analysis in the paper seems to be in the NTK regime. In fact, the paper relies on a number of results proved in the past works on NTK. There are some caveats with these results that the authors never brought up in the paper. \n      - First, most of the past works on NTK assume certain kind of initialization for the NN. But the initialization scheme used in Algorithm 3 doesn't match with the past works. Given this, do the past results carry over directly to the setting in this paper? In particular, do Lemmas E.6 to E.10 follow directly from past works? \n      - Second, the result in Theorem 4.2 doesn't say anything about how the context vectors are generated suggesting that the result holds even if the context vectors are generated adversarially. But I doubt if this is the case. The NTK results such as the ones in [2] require the context vectors for all the rounds to be generated by an oblivious adversary before the start of the algorithm. If the context vectors are generated adversarially, the NTK analysis in these works doesn't go through. Can the authors comment on this?\n\n* Experiments Issues:\n  - I have a concern regarding how the ML classification datasets are converted to the collaborative bandits problem. Based on the description in Appendix A.2, it looks like the reward function for any given context vector is the same for all the users (i.e., h_u(x) is independent of u). This suggests that there is a single cluster for any given arm. If this is the case, the problem simply boils down to the neural contextual bandit problem studied in [2]. Then, why is there a huge difference in performance between the proposed technique and NeuUCB-ONE?\n\n\n[2] Zhou, Dongruo, Lihong Li, and Quanquan Gu. \"Neural contextual bandits with ucb-based exploration.\" In International Conference on Machine Learning, pp. 11492-11502. PMLR, 2020.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Yc7myQnvn-", "reviewer": "Reviewer_ygez", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "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": "", "main_review": "", "summary_of_the_paper": "\nThe paper studies Neural Collaborative filtering bandits that incorporate collaborative effects among users with both linear or non-linear reward assumptions, and proposes a meta-learning based bandits algorithm (Meta-Ban) that could adapt to dynamic groups with a UCB-type exploration. It then provides theoretical analysis on its regret upper bound for the proposed algo, Meta-Ban, and evaluate them on 10 datasets and show that the proposed algorithms outperforms against baselines. ", "summary_of_the_review": "\nThe paper studies Neural Collaborative filtering bandits that incorporate collaborative effects among users with both linear or non-linear reward assumptions, and proposes a meta-learning based bandits algorithm (Meta-Ban) that could adapt to dynamic groups with a UCB-type exploration. It then provides theoretical analysis on its regret upper bound for the proposed algo, Meta-Ban, and evaluate them on 10 datasets and show that the proposed algorithms outperforms against baselines. \n\nOverall it was an interesting and important problems. However, it also raised many of questions that were not clear in the paper in terms of what assumptions for a couple of 4 challenges they aim to tackle in the paper, and how does assumptions and structure properties on these challenges could impact the efficacy and performance of the proposed algorithms. Please see some detail questions below: \n- In the first step of the proposed algos, it would like to infer a user's relative group. The question is what assumptions made on these relative group? are they independent? can a user belong to multiple groups? If they are dependent, how does it impact the algorithm in terms of regret analysis and performance? Also, what are constraints or structure properties do we want to place when designing relative group? \n- In Challenge 1, the paper also asked whether the returned group is the true relative group, but was not clear on its importance and what's the consequence if it is not true relative group (sorry if overlook). \n- in Page 4 when defining Group Inference, the paper mentioned that it is natural to use the universal approximator. Could they explain intuition on why and this is chosen? \n-  In challenge 3, the paper mentioned the rapidly-changing relative groups, and wonder if the authors could provide more detail information on what mathematical assumptions and properties on them, as they would likely impact how we think/propose solutions in terms of efficacy and efficiency. ", "strength_and_weaknesses": "Strengths: \n- The paper studies Neural Collaborative filtering bandits that incorporate collaborative effects among users with both linear or non-linear reward assumptions, and proposes a meta-learning based bandits algorithm (Meta-Ban) that could adapt to dynamic groups with a UCB-type exploration. \n- the paper provides theoretical analysis on its regret upper bound for the proposed algo, Meta-Ban, and evaluate them on 10 datasets and show that the proposed algorithms outperforms against baselines. \n\nWeakness or questions: \n- In the first step of the proposed algos, it would like to infer a user's relative group. The question is what assumptions made on these relative group? are they independent? can a user belong to multiple groups? If they are dependent, how does it impact the algorithm in terms of regret analysis and performance? Also, what are constraints or structure properties do we want to place when designing relative group? \n- In Challenge 1, the paper also asked whether the returned group is the true relative group, but was not clear on its importance and what's the consequence if it is not true relative group (sorry if overlook). \n- in Page 4 when defining Group Inference, the paper mentioned that it is natural to use the universal approximator. Could they explain intuition on why and this is chosen? \n-  In challenge 3, the paper mentioned the rapidly-changing relative groups, and wonder if the authors could provide more detail information on what mathematical assumptions and properties on them, as they would likely impact how we think/propose solutions in terms of efficacy and efficiency. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2u_32wKsCfA", "reviewer": "Reviewer_2vmf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper the authors study the collaborative effects among users in order to improve recommendations. This line of works is known as collaborative filtering bandits. \nThe authors propose an interesting approach for this problem. Rather than assuming a linear model between the arm features and the expected reward, they use a neural bandit approach that allows dropping the linear assumption. Rather than using a clustering algorithm for capturing the collaborative effect, they define a relative group as a set of users that have similar expected rewards on the same item. Then, for each group (i.e. for each item) they learn a meta-neural bandit that shares historical data between users of the same group. The choice of the item for user u_t is done at the group level. This allows capturing collaborative effect among users. A neural bandit per user is also learnt in order to approximate the expected reward of items for the considered user. This allows building the estimated relative groups. \nThe proposed algorithm is analyzed using over-parameterized neural network regime. They improve by a factor \\sqrt{\\log T} the previous results of (Zhou et al 2020). Moreover the obtained pseudo-regret upper bound does not depend on the dimension of arm features. They also provide a high probability guarantee on the time spent to find the true relative groups.\nFinally, the proposed algorithm is favorably tested with respect to baselines on different datasets.\n", "summary_of_the_review": "Despite some drawbacks that the authors can fix, overall it is a good paper. \n_______________________________________________\nI read the rebuttal and I thank the authors for their answers.", "strength_and_weaknesses": "The paper is well written. Theoretical and experimental evidences of the efficiency of the proposed algorithm (Meta-Ban) are provided. \n\nHowever, the reviewer has some comments and questions.\n\n1/ The authors assume that the reward is bounded, but the noise seems to be unbounded. So it seems that equation (1) is not accurate. Why do the author not assume a sub-gaussian noise as in (Zhou et al 2020)?\n\n2/ The authors use the over-parametrized neural network framework to analyze their algorithm, and they show a \\sqrt {log T} regret bound improvement in comparison to the state-of-the-art. But in comparison to the state of the art, the regime where the neural network is analyzed is even more unrealistic than that of the state of the art. Indeed at each time step, the needed number of steps of the gradient descent in the order of T^56, while it was in \\tilde O (T) in (Zhou et al 2020).\n\n3/ In the experimental section, the value of J_2 is not given. I suggest to the authors to reassure the reader by giving the used value of J_2.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0CILeRbhZYQ", "reviewer": "Reviewer_GgGh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper explores the neural collaborative filtering bandits problem. Specifically, the authors first introduce relative groups to formulate groups given a specific content. Then, they use a meta learner and user learners to learn non-linear and linear reward functions. The authors also claim that this is the first work incorporating ‘collaborative effects’ in neural bandits. Besides experimental results, the authors also provide theoretical analysis of the regret upper bound of complexity, in which it is sharper than existing related works.", "summary_of_the_review": "All in all, although the analysis is good, I personally found the experiments are a bit shallow towards recommendation. The authors should focus/provide more experiments on recommendation datasets such as Netflix, and also with more baselines towards personalized recommendations. In addition, I am also curious to see deeper analyses of run time, complexity, and scalability issues with dealing with large-scale systems.", "strength_and_weaknesses": "Strength:\n\n1. The presentation of the paper is intuitive and easy to understand. The authors introduce four challenges (i.e., C1-4) and subsequently tackle each challenge, which make it easy for the readers to follow\n2. This is good that the authors also provide pseudo-code for Meta-Ban, with GradientDecent_Meta and GradientDecent_User.\n3. The authors also have good regret analysis (Section 4), in which it shows that the proposed method is comparable with existing clustering of bandits and neural bandits\n4. The experiments show that Meta-Ban outperforms all baselines across datasets over 10 runs, according to Figure 1-2.\n\nWeaknesses: \n\n1. Although the experiments yield good results, I believe the authors should focus more on recommendation datasets/tasks, rather than ML datasets. Specifically, among all the datasets used in the paper, only two of them (i.e., MovieLens and Yelp) are common recommendation datasets. In addition, the preprocessing steps in Appendix A.2 seem to be not common in my opinion. For example, “If the user’s rating is less than 2 stars (5 stars totally), its reward is 1; Otherwise, its reward is 0” or “we use K-means to divide users into 50 clusters”. Could you please give more explanations of the preprocessing steps? How did we decide the ‘threshold’ of 2 stars to set the reward of 1? How did we come up with 50 clusters? Can we have more/less clusters? \n2. Also from Configurations paragraph of Appendix A.2, the authors use only a simple neural network of 2 fully-connected layers, which is a bit surprising to me as this paper introduces neural collaborative filtering bandits but with only a simple neural network of 2 layers. Can we have a larger neural network with more layers? If not, why? \n3. In Section 5 Experiments, NeuUCB-ONE and NeuUCB-IND seem to perform quite well. Would it be possible to combine NeuUCB based models with ‘relative groups' and compare them with Meta-Ban? Moreover, can we also compare Meta-Ban with NeuMF [1] beside NeuUCB-* so that we can compare our method with two groups of baselines: i) neural network and ii) neural network + bandits for personalized recommendation tasks? \n4. In the Appendix A.5, the authors mentioned that “This fluctuation is acceptable given that different input dimensions may contain different amount of information”. How can we determine if the fluctuation is ‘acceptable’?\n\n[1] Neural Collaborative Filtering. WWW 2017.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject