Laplacian Kernelized Bandit
Authors: Shuang Wu
Arash A. Amini
Venue: ICLR 2026 Poster (2026)
Keywords: Bandit Problem
Kernel Method
Graph Laplacian Regularization
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

Abstract: We study multi-user contextual bandits where users are related by a graph and their reward functions exhibit both non-linear behavior and graph homophily. We introduce a principled joint penalty for the collection of user reward functions $\\{f_u\\}$, combining a graph smoothness term based on RKHS distances with an individual roughness penalty. Our central contribution is proving that this penalty is equivalent to the squared norm within a single, unified _multi-user RKHS_. We explicitly derive its reproducing kernel, which elegantly fuses the graph Laplacian with the base arm kernel. This unification allows us to reframe the problem as learning a single "lifted" function, enabling the design of principled algorithms, LK-GP-UCB and LK-GP-TS, that leverage Gaussian Process posteriors over this new kernel for exploration. We provide high-probability regret bounds that scale with an _effective dimension_ of the multi-user kernel, replacing dependencies on user count or ambient dimension. Empirically, our methods outperform strong linear and non-graph-aware baselines in non-linear settings and remain competitive even when the true rewards are linear. Our work delivers a unified, theoretically grounded, and practical framework that bridges Laplacian regularization with kernelized bandits for structured exploration.

Published as a conference paper at ICLR 2026
LAPLACIAN KERNELIZED BANDIT
Shuang Wu Department of Statistics UCLA
Arash A. Amini
Department of Statistics UCLA
Los Angeles, 90095, USA shuangwu2228ucla..
Los Angeles, 90095, USA aaamini@stat ucw.eucclcc.oooo
ABSTRACT
We study multi-user contextual bandits where users related by graph and their reward functions exhibit both non-linear behavior and graph homophily. We introduce principled joint penalty for the collection of user reward functions {fa}. combining graph smoothness term based on RKHS distances with an in- dividual roughness penalty. Our central contribution is proving that this penalty is equivalent to the squared norm within a single, unified multi-user RKHS. We explicitly derive its reproducing kernel, which elegantly fuses the graph Laplacian with the base arm kernel. This unification allows us to reframe the problem as learning single "lifted" function, enabling the design of principled algorithms. LK-GP-UCE and LK-GP-TS, that leverage Gaussian Process posteriors over this new kernel for exploration. We provide high-probability regret bounds that scale with effective dimension of the multi-user kernel, replacing dependencies on user count or ambient dimension. Empirically, our methods outperform strong linear and non-graph-aware baselines in non-linear settings and remain compet- itive even when the true rewards are linear. Our work delivers a unified, theo- retically grounded, and practical framework that bridges Laplacian regularization with kernelized bandits for structured exploration.
INTRODUCTION
Graphs are pervasive in modern sequential decision-maker encoding similarity or interaction among entities like users, items, or sensors. In a multi-user contextual bandit setting, this graph structure is informative since it provides pathway to share information, allowing an algorithm to learn more efficiently than if it treated each user in isolation. We study the problem where known user graph promotes homophily, meaning connected users tend to have similar reward functions. At each round t, learner observes an arm HG E Dr, and receives noisy reward yt- Naively learning a separate model for each user inefficient, leading regret that scales with the number of users. Exploiting the graph structure, however, can yield dramatic improvements in both sample efficiency and performance Szorenyi al. (0013): Landgren et (2016); Gong Zhang (2025); Wang al. (2025).
u, and set of available arms (contexts) D3 C Fdd selects
This problem was first formalized as the Gang of Bandits (GOB) Cesa-Bianch et al. (0013). which models the collection of user reward functions (-) as a smooth signal the graph. Seminal works like GoB Lin Cesa-Bianchi et al. (2013) assume linear reward functions, Ja (xx 0 æ, and penalize roughness via the graph Laplacian, leading to the effective linear bandit solution. Sub- sequent research has extended this approach with improved computational scaling Vaswani et al. (2017): Yang al. (2020), but has largely remained within the linear paradigm. Yet, in many appli- cations, from recommendation systems personalized medicine, reward functions exhibit complex, non-linear behavior. While rich literature on kernelized bandits exists to handle non-linear rewards for a single agent Chowdhury & Copalan (0017): Du al. (2021); Bubeck et al. (2021); ); Li et al. 2002);: Zhou & Ji (2022), principled methods for the mulli-usee graph setting are less developed. Existing approaches construct multi-user kernel heuristically
product of user and arm ker- nels Dubey et al. (2020), leaving a gap between the intuitive modeling goal and the final algorithm.
We refer Appendix for further discussion of the related work.

---

Published as a conference paper at ICLR 2026
Our work bridges this gap, starting from natural first principle for this problem. A desirable collection of reward functions {fu [ful==1, where each fu lies in a Reproducing Kernel Hilbert Space (RKHS) H.,, should be jointly regularized: they should be smooth across the graph (homophily) and individually well-behaved (low complexity). We formalize this via an intuitive, additive penalty that combines graph smoothness term with a standard ridge penalty. In the scalar case without arm features, this type of iaplacian-basee regularization is known to induce a kernel whose matrix is the (regularized) Green's 's function of the graph [Smola & Kondor (2003). Building on this connection, we show that the same principle extends to the multi-user contextual setting: the joint penalty defines the squared norm of single, lifted function f(x, u) := fu(2)) in a unified multi-user RKHS. We explicitly derive the reproducing kernel for this space, which elegantly fuses the graph Laplacian L "u,
and the base arm kernel Kz: [(a;, u), (a', n()) I K₂ (2. x'), where L, L + pl the regularized Laplacian.
This unifying perspective transforms the problem of learning n related functions into the elegant problem of learning a single function in a well-defined kernel space. It allows us to directly apply the powerful machinery of Gaussian Process (GP) bandits Srinivas et al. (2009): Krause & Ong Vakili et al. (202T). We develop LK-GP-UCE and LK-GP-TS. algorithms whose principled uncertainty estimates are derived from the GP posterior of this unified kernel, enabling them to naturally and jointly leverage non-linear
structure and Laplacian homophily. We provide regrett guarantees for these algorithms in terms of an effective dimension that captures the spectral interplay between the graph and the kernel. Our experiments show that our methods are competitive in linear regimes and substantially outperform both linear and non- won-graph-awar baselines when rewards are non-linear yet graph-smooth.
Our main contributions are:
We formalize the generalized gang-of-bandits problem with a principled joint penalty combining graph smoothness and RKHS regularity for the collection of reward functions {fu]a
We prove that this penalty is equivalent to the squared norm in single multi-user RKHS and explicitly derive its reproducing kernel, unifying the graph and arm structures.
We develop LK-GP-UCK and LK-GP-- -1---GP---- -TS, GP-based bandit algorithms that leverage this unified kernel for principled and effective exploration.
We provide novel regret bounds in terms of an effective dimension that depends on the spectral properties of both the kernel and the graph Laplacian.
We empirically validate approach, demonstrating significant performance gains over strong baselines in settings with non-linear, graph-smooth reward structures.
Notations. Let [n] be set 21,2...., n2. For set or event ε, we denote its complement as E. Vectors are assumed to column vectors. e; the i-th canonical basis vector in R., I is the identity matrix. (Ai represents the minimum eigenvalue of matrix A. & is the Kronecker product. Denote the history of randomness up to (but not including) round as F, and write P-(-) == PP- ((F)) and E.(-) == Ei [FF] for the conditional probability and expectation given Fe. We use for big-O notation up to logarithmic factor and x represent asymptotically equivalence in rate of growth for any two functions.
PROBLEM FORMULATION
2.1 GANG OF BANDITS WITH NON-LINEAR REWARDS
We consider multi-user contextual bandit problem, often called Gang of Bandits (GOB) Cesa- Bianchi al. (2013), with n users and a potentially infinite set of arms. We denote the set of users as U (1,... ........ n and the arm set as D C Rd, where each arm is represented by a feature vector x E D. The users are connected by known undirected graph G = (4, where & is the set of edges. Let W E pax= be the matrix of non-negative edge weights way. and D be the diagonal degree matrix with entries d, := E, Wij. The corresponding graph Laplacian is := D W.
The learning process unfolds over T rounds. At each round t E {1...., T). the environment presents user u, U (for example, randonly/unifornly pick one) and finite subset of avail-
2

---

Published as a conference paper at ICLR 2026
able arms Di S D. The learner selects observes a noisy reward: Yr = fu, (xt) + & where {fu D + R] is collection of unknown reward functions, and sub-Gaussian with variance proxy o², given the history of interactions Jt. For the illustrative purpose, use fI:= = {fu]u=r as the collection of the user-level reward functions.
2t E D, following some decision policy and
for each user. The noise term is assumed to be conditionally zero-mean
The learner's objective is to minimize cumulative regret. The instantaneous regret incurred at time t is A, fu, (xi)
(xx) where 2t arg maXzeD, fu, (2) and and cumulative regret over T' rounds is defined as Rr = Ei=1 A. A successful algorithm must achieve sub-linear regret, RT/T TT + 0 as T + oo, ensuring that the average per-round regret vanishes.
2.2 PRINCIPLED REGULARITY MODEL FOR GRAPH HOMOPHILY
To make learning tractable, need impose regularity on the unknown functions fin. We make two core assumptions. First, we assume that each function fu is individually well-behaved, be- longing to a common Reproducing Kernel Hilbert Space (RKHS), denoted Hz. with positive semi-definite kernel K2 D x D + R. The associated feature map is denoted as ş such that (a x') = arm features.
This captures the non-linear structure of rewards with respect to
Second, we formalize the notion of graph homophily by assuming that users connected by an edge in G' have similar reward functions. This user similarity is measured by the squared distance be- tween functions in the RKHS, |lfi - f Combining these principles, we model the true reward functions having small joint penalty that balances graph smoothness with individual function complexity:
n
n
PEN(fin:P)
Σ :-=1
Wiyl fl
1i.. tp
Lplesff
(1)
2
PEN grapi (fi.n)
PEN,idge (fim)
where p > is regularization hyperparameter and Lp := L + pl is the regularized graph Lapla- cian. This penalty is central to our framework, as provides a clear, interpretable objective for modeling related, non-linear functions.
2.3 FROM JOINT PENALTY TO UNIFIED MULTI-USER KERNEL.
Our key theoretical insight is that the intuitive, additive penalty in equation I is not merely ad- hoc regularizer. It is, in fact, the squared norm single, unified Hilbert space over the user-arm product domain 21 D. This allows us reframe the problem from learning related functions to learning one "lifted" function, f(x, u) == fa(x)) in this new space. We show that it is the squared RKHS norm for the product space
HH @ H2 where Ho is the RKHS with kernel
KG(u, u, w') = | Ju. in the following theorem.
Theorem 2.1 (Multi-user Kernel). Let Hy be an RKHS of functions on 'D with kernel K The vector space of function collections H {(f1.... su Ho, Vu U} equipped with the inner product
(f.9)
Σ Lole $-==
is a Reproducing Kernel Hilbert Space of functions on U x D. The associated squared RKHS norm precisely the peralty in equation 1 and reproducing kernel K (D 11)2 is given by:
K K(xx,u) ((), =14, -1= (x(,
This result is powerful: it provides direct, canonical construction for a multi-user kernel that fuses graph and feature information. The kernel K2 captures similarity between arms, while the matrix Lp (the graph Green's function) captures similarity between users, with [L_ " measuring the strength of connection between users u and v/ through all paths in the graph. See Appendix A for more background.
3

---

Published as a conference paper at ICLR 2026
This unification allows to represent the lifted reward function f(z, u) via feature map d( u) such that f(x, u) = (0, of æ u)) for some (potentially diinite-dimensionn (o(x, u), o( rd))- Formally, for context-user pair (æ, u) E D x U, the feature map Ø is defined as (x u) == Lp L eu @ ((x). The problem is now cast as learning a single function in the multi-user RKHS H. This insight paves the way for a principled algorithmic approach based on Gaussian processes, which we detail next.
parameter 0, and
(( u), (x', ))))
3 LAPLACIAN KERNELIZED BANDIT ALGORITHMS
The identification of the multi-user RKHS with its explicit kernel K provides a powerful, unified framework for the GOB problem. It allows to model the entire system- across all users and arms-w with a single Gaussian Process (GP), sidestepping the complexity of managing n separate but correlated models.
3.1 A GAUSSIAN PROCESS PERSPECTIVE
We propose algorithms based on the Gaussian process (GP), motivated by the kernelized bandit literature (Chowdhury & Gopalan (017). Our Bayesian modeling is only assumed for derivation of our estimators and it is not necessarily the true model. We place GP prior over the unknown lifted reward function f U RR denoted as
K [fi(-)...., fa(-)] ~ ((.)).(..)) (-,))).
where K is the multi-user kernel defined in equation {(o,, w))e=n This proir implies that ft == [Su (.=1).... Su, (0x)] ~ N(O, K,) where K, E
For any finite set of user-arm pairs
gext with entries Kels = [(x,, u.), (zy, uy)) ) the kernel matrix.
At round t, given user us and selected arm ær, the Bayesian model assume a reward model y/ far, ue) + ez where e NO, A) is the noise. Therefore, conditioned on the history Fr, the posterior distribution for (ax is N (P),)-1(Z) (2). (z))-(())), with the posterior mean and variance:
(x) (x, u) T (K, + AI,) "
- (x) K K(xx, u). (xx, u)) (xx, u) T (K₁ + -I)) kk, u).
Here (e u) = [K u1); (x, u))...., (((),, ue), (x, u))] E R$ the kernel vector be- tween past selected user-action pairs {(x2, (o))== and new pair (æ, u), and y: = [y1.....,t. R is the observed reward.
Remark 1. When {lue, xx)) is fixed (deterministic) sequence, under this model we have yel ft ~ (fe,, AIe) and ft ~ NO, K.). Then, the mutual information between and fi is Ki), which is often referred as the information gain of 2009 Section 2.. For convenience, we write
given by: 1yy6 ft) = log det I,, the Bayesian model (Srinivas et al.
(4) and refer to it the information gain round although it is twice what is usually called the information gain in the literature. Moreover, Ttt in our notation depends on the sequence, although in the literature, this symbols is often used for the maximum information gain over all sequence {(u,, xt))T= of length T.
7/ := log det (Ie --
Connection to Regularized Regression. It is worth noting that the GP posterior mean estimator in equation is equivalent to the solution of an offline Kernel Laplacian Regularized Regression (KLRR) problem. Specifically, the function f H that minimizes the regularized least-squares objective
min Σ (f(,,, ya)² A|ll EEN
(S)
precisely the posterior mean function ( based algorithm is deeply connected to the batch learning principle of minimizing prediction error regularized by our proposed multi-user RKHS norm from equation] I
(x, u). This equivalence confirms that online, GP-
4

---

Published as a conference paper at ICLR 2026
3.2 DECISION STRATEGIES: UCB AND THOMPSON SAMPLING
With these posterior estimates, we can design bandit algorithms that effectively balance exploration and exploitation. We propose two algorithms based on common and powerful heuristics: Upper Confidence Bound (UCB) and Thompson Sampling (TS). The complete procedures are described in Appendix E.
Laplacian Kernelized GP-UCB (LK-GP-UCB) Following the principle of "optimism in the face of uncertainty," " our UCB algorithm selects the arm with the highest optimistic estimate of the reward. At round I, upon observing user W, and arm set Dr, it chooses:
at arg max mED;
(uu,et- + Br
where 3e the hyperparameter that ensures the appropriate scale of exploration via confidence width Tu,,t-1(c)) (ar). Our theoretical analysis provides explicit form for 3e in Theorem 4.2 to guarantee low regret, though in practice it is often treated as a tunable hyperparameter.
Laplacian Kernelized GP-TS (LK-GP-TS). Thompson Sampling Thompson 1933 Russo al. (0188) operates on the principle of "probability matching." At each round, it draws a random func- tion from the posterior distribution and acts greedily with respect this sample. A practical way implement this is to select the arm that maximizes sample from the posterior predictive distribution for the reward:
arg max (Hu),e-((0)) + us ( wED;
where Vt is the scale hyparameter for exploration and 24 (œ) ~ No 1) is the Gaussian perturba- tion. Aligned with common Thompson Sampling literature, decision strategy in equation 7 can be separated into two steps: sampling (x) from N (( ofo2 1 (x)) for all æ E De and choosing an arm by 2 = arg max 74 (x). Similarly to the UCB algorithm, we also use the explicit theoretical choice for 242 in Theorem 4.3 while it is tuning hyperparameter in real application.
3.3 PRACTICAL IMPLEMENTATION
A naive implementation of the posterior updates in equation is computationally expensive, requir- ing an O(t)) matrix inversion each step. To ensure practical scalability, we can use recursive formulas to update the posterior mean and variance in O(t²) or, for fixed grid of points, even more efficiently. Specifically, we can maintain and update the inverse matrix (K, + AA)) -1 or use the following recursive updates for the posterior estimators Chowdbury & Gopalan (0017):
(a))(2r)= 1u,e-1(x)) + 2t 4t-1((2) ((x, w), (Ir,, (x), u4)) (y: 1
X + (xx))
qe (e((,, w), ,()) = u). (x', u()) 9 90-1((2, u), (x),, uz)) 1119911110 ((D u)), ,())
(8)
+ 02 2
(x)) ( q ((x, u), (x),
- (2re)
where qx w), (x', u/) is the estimated posterior covariance round t. We explain how obtain the updates in Appendix E.2 hybrid approach that uses exact inversion for small and switches to recursive updates for larger can balance numerical stability and computational efficiency. Further details on our implementation are provided in Appendix F4
4 REGRET ANALYSIS
We provide theoretical guarantees for proposed algorithms. Our analysis is built upon high-proban gigh-probbbility confidence bound for our GP posterior estimates, which turn leads to sub-linear regret bounds for both LK-GGPUCCH and T.K-GPTT.

---

Published as a conference paper at ICLR 2026
4.1 ASSUMPTIONS
Our results rely on the following standard assumptions.
Assumption 1 (Sub-Gaussian Noise). The noise process {<t]E=) is Fy-measurable stochastic process and is conditionally sub-Gaussian with constant o².
Assumption 2 (Bounded Base Kernel). The base arm kernel K=(+,) is positive semi-definite and its diagonal is uniformly bounded: sup=ED K (x; x) S a² for some a >
Assumption 3 (Bounded Multi- User RKHS Norm). The true lifted reward finction f has a bounded norm in the multi-user RKHS H: || = PEN(JimiP) S fo some constant Bp >,>>0 0.
Assumption 1 is common assumption in bandit literature. Assumption 2 and indirectly align with the regularity assumptions in kernelized bandit and graph smoothness literatures [Bllin et al. 22006;; Kocák et al. (2020). These assumptions imply that the rewards and the multi-user user kernel are bounded. Formally, we have
K ((xx, u), u)) S Kmax == a² maax L 1p.a (mxu)
sup
uEll
4.2 HIGH PROBABILITY CONFIDENCE BOUND
The core of our regret analysis is the confidence bound that relates the true function f our pos- terior mean estimator Pe. This result quantifies the model's uncertainty and justifies the exploration strategy of the UCB algorithm.
Theorem 4.1 (Confidence Bound). Suppose Assumptions and hold. Let ((2 ]e be the Fe-1-measurable discrete time stochastic process. Then, using the posterior estimators paae (2z) and (x) in equation 3 yields to a high probability upper bound: for any 8 E (0, 1), with probability least 8, for all and all (xx D x U:
(1x))(ar) - f(x,, w)) S SBc (x,x())
where the confidence parameter Be is given by
1 2 22og + log de A- X-1Kk)
Bg Bp +
(10)
This confidence bound follows structure similar to those in the kernelized bandit fttrratur/Chhwdl Chowd- hury & Gopalan 22177: Valko et al.] (203)); Dubey et al. (2020). but our analysis offers two key distinctions. First, proof does require the constraint À 2 1 found in some prior work. More significantly, we retain the term log det det(1, + A- K.) directly within our confidence width 3r This contrasts with classical approaches that often proceed by further bounding this term using information-theoreiic quantities, which can result in looser bounds. By keeping the exact term, we the stage for tighter, data-dependent analysis via the effective dimension.
4.3 REGRET BOUNDS VIA EFFECTIVE DIMENSION
To obtain concrete regret rates, we characterize the growth of the log det term using the notion of an effective dimension.
Definition 4.1 (Effective Dimension). The effective dimension d of the learning problem, given the sequence of actions up to time T, is defined as:
d == log det KT/
(11)
log(1 + TT mr'Kmax/D
This quantity, inspired by recent work in kernel methods and overparameterized models Wu & Amini (2024); Bietti & Mairal (2019); Yang & Wang (2020), measures the intrinsic complexity of the learning problem. It can be interpreted as the ratio of the sum of log-eigenvalues of the matrix Ir + Kr/A A to a bound on the maximum possible log- cigenigeev (T'Knax is an upper bound on the largest eigenvalue of Kr). As such, it serves robust, graph-dependent measure of the matrix's rank, capturing the "dimensionality" of the function space actually explored by the algorithm.
Using the confidence bound Theorem 4.1 and in Definition 4.1 we provide the regret upper bound for I.K 1.K-GP-UCR and LK-GP-TS as follow.

---

Published as a conference paper at ICLR 2026
Theorem 4.2 (Regret Bound of LK-GP-UCB), Suppose Assumptions] 2 and 3 hold, with no sumption on the number of arms. By setting the exploration parameter 3t in LK-GP-UCB to St from Theorem 4. the cumulative regret is bounded with high probability
Rr = =(ddo(]g(T)V)) ((dTT)
Theorem 4.3 (Regret Bound of LK-GP-TS), Suppose Assumption 7 aand and the decision sets Dj are uniformly finite. By setting the exploration parameter Vi in LK-GP-TS to Be from Theorem 4.1 the cumulative regret is bounded with high probability as:
Rx =
VT) = (dvTT)
These bounds demonstrate the efficiency of approach. The regret scales not with the number of users the ambient feature dimension, but with the effective dimension d. For problems where the graph and kernel structure lead to rapid spectral decay, d can be significantly smaller, resulting in substantial gains in sample efficiency.
In the notation of Remark the effective dimension d scales as: d= Yr/ log(1 + TK maxx/ / /\) x "Y
TogT where the approximation assumes X = (()). The interpretation of d as dimension is evident in the linear setting (n 1 with linear kernel on Rd), where TT OOd T') (Srinivas al. 2009 Theorem 5), yielding d = (d). This example demonstrates that our bound (dy/T) is tight up to logarithmic factors for infinite action spaces, matching the minimax optimal rate (dv for linear bandits Dani et al. (2008).
For uniformly finite action spaces ((2r) < M for all t), is possible to achieve a tighter regret bound of Ö( v dd)) using algorithms such as SupKernelUCB Valko al. (013). This improvement relies on scaling the exploration parameter as 3, x 1/vī rather than using equation 10 effectively removing factor of //r. Since our primary contribution is the construction of the unified multi- user kernel, such algorithmic refinements from the kernel bandit literature are directly applicable to framework.
4.4 SPECTRAL ANALYSIS OF THE MULTI-USER KERNEL
To interpret the effective dimension d, we analyze the spectrum of the multi-user kernel K. By Theorem 2.1 K K Kz, the tensor product of the user kernel KG associated with matrix Ko L and the arm kernel K2- Consequently, the eigenvalues of the integral operator associated with
K are the pairwise products of the marginal eigenvalues. Let { Im be the eigenvalues of Lpp and 5 be the eigenvalues of Kg. The operator eigenvalues for K are then {uy X, ( hag. The eigenvalues of the normalized matrix / approximate these operator eigenvalues
In particular, obtain the following approximate upper bound the information gain y/:
[ T V52 = >
TT = log (I + + KT)
log 1+
(12)
where : :=))== - log(1 + swy)) represents the information gain of single-user problem with effective signal strength We know that (((s) is concave and sublinear, e.g., for the squared exponential kernel on Rd, (s(s S (log s)d+1 (Srinivas et al. 2009 Theorem 5)), hence function Tf YT grows slowly T. What interesing then the dependence on n.
While informative, the bound in equation 12 can be conservative for finite T (see Figure I A sharper bound similar vein can obtained by considering a regular design: assume we observe each user exactly := T/n times, choosing the same set of actions {æ),-.. , for all users. By permuting round indices such that all observations for user appear first, followed by user 2, etc., the eigenvalues of K remain invariant. Under this setup, Kr = K Khuse where @ is the matrix Kronecker product and K Khuse hase is the m x m kernel matrix evaluated on the common action set. Let (6x) = be the eigenvalues of baaase /m. The normalization by m ensures that Dz stabilize around the population eigenvalues U for large m.
'This holds asymptotically T + under i.i.d. sampling Koltchinskii & Ging (0000; results from Srinivas al. 2009 Theorem 5) suggest similar approximation holds for worst-case sequences.
7

---

Published as a conference paper at ICLR 2026
reependom: It
Shinng Homoetly load
3208
(a) Two bounds vs, Actual
(b) d vs. (log (empty graph) (c) d vs. (log TY (complete graph)
Figure I: Rank Collapse: (a) Comparing the growth of the actual information gain "r vs n i.i.d. design (red) versus the two bounds equation 12 (blue; crude) and equation 13 (green; nearly exact) in complete graph. The kernel exp(-II= y|l /2). u, ~ Unif( [n]) and 2, Unif[o, 1]a where d Panels (b) and (c) show the growth of d vs. T) under empty and complete graphs, respectively. Note that under the complete graph, d slightly decreases as increases.
Consequently, the eigenvalues of KT/T given by Dz /,, yielding the exact expression:
T nd
TT-
log 1+
T
nd 2
(13)
where (s) Dn= log(1 + sbn)) represents the "empirical" information gain of single-user problem with common actions. For large enough -T/n, we have D Vz and (s) = (sss). Expression equation [3 exact for regular designs and, as shown in Figure [ provides sharp approximation for the i.i.d. sampling case. We use equation 13 to analyze across graph structures.
-p-l_ and XÇ =p- for v T npa Thus, the effective dimension scales as n times the single-user effective dimension. For example, with an SE kernel,
Case 1: Independent Users (Worst Case). If L = 0. then KG indep
all [n]. The gain sums linearly: "r Ei=1 V (AT
((T
d On (log(T/n)) which remains sublinear in T.
Case 2: Strong Homophily (Complete Graph). To isolate the effect of an extremely dense user graph under homophilous prior, consider complete graph with edge weights Waj 1. The Laplacian eigenvalues are (multiplicity 1) and (multiplicity n - 1). The kernel eigenvalues invert this structure, with d andand and Aç 1/(n++ + p) for Z 2.. For large n, this yields a nearly rank-1 I matrix. Substituting into equation 13 provides "Head + Tail" decomposition:
clique TT
T ppd
+ (n 1)4
T n(n + p)}
(14)
This leads to the following consequence:
Proposition 4.1. Consider the regime where T S Cn for some constant C. Then, under regular
clique design: VT ( + O(I.
Proof. Using log(1 + x) < x for x 2 O. have vi(s) s(E D4). Then, for T S Cn.
(n (n- n(n p)d
T
S nú
(n PJX ( Sn.
C
C
C X
(n p)X
5=1
since =
Similarly, for the first term, (TT)) < C ph
This bound holds for any kernel whose integral operator is trace class. For unifromly bounded kemee as in Assumption 2
have the straightforward bound Σ m E/ tr Khase) \/m a.
8

---

Published as a conference paper at ICLR 2026
1000
Cumulative regres-
600
1:0
300
100
230
50-
200
900
800
000
1000
500
1000 Round
1500
2000
500
1000
1500 Round
2000
2500
3000
Round
Cocp fereelice
608 Un
UCB
Graghica
UKIGTTS
UK
UCC
Pertzer
Rooled LinUCe
Figure 2: Cumulative Regret under Linear-GOB regime. From left to right are tasks easy level, medium level, to hard level.
1500
Cumulttvve eagret
1250
2000
1000
750
500
1000
Kemnelic
G08.LI
GraphUCS
LICOPTSS
LC-GU
Pertse-Linuce
Pooles-LinUCS
Figure 3: Cumulative Regret under Laplacian- Kernel regime using GP draw. From left to right tasks of easy level, medium level, to hard level.
This result significant: in the regime S Cn, the information gain grows with neither n nor T, implying d = (11/log (slowly decreasing). This behavior has no counterpart in the single- user setting and confirms that under strong homophily, regret is independent of n. These theoretical findings are corroborated by our empirical plots in Figure
Generalization to Clusters. If the graph contains & disjoint clusters with high internal connectivity, KG will have eigenvalues of magnitude ((1) and n n- k magnitude O11/n). A similar argument implies that = Okk lo) when T < Cn. Thus, essentially counts the number of significant eigenvalues of the normalized kernel Kg, serving a soft proxy for the number of distinct user clusters.
Comparison with Independent Bandits. It is instructive to compare this with independent learn- ers that share no information. Since each user generates T/n observations on average, the regret for learning each function is at best /T/n, yielding an overall regret of Σ /T/n VnT. In the worst case (Case 1), our bound d'T scales nvT (ignoring log factors), which is factor of /n looser than the independent baseline, However, had we assumed uniformly finite action space, we could achieve regret bound of VdT VnT, matching the optimal independent rate.
The advantage our approach becomes evident under strong homophily. For independent learners in the regime T x n, the regret scales as VnT = T, meaning no learning occurs. In contrast, we showed that our Laplacian Kernelized Bandit achieves regret of O(VT) in this regime (up to log factors). A similar improvement holds when there k ((1) strong clusters.
5 EXPERIMENTS
We evaluate Laplacian Kernelized bandit algorithms, LK-GP GP UCB and LK GP thetic data environments that capture user-user homophily known graph while varying reward structure (linear vs. nonlinear) and problem difficulty. Baseline algorithms include GraphUCg Yang
GD-GG--TT -S on several syn-
et al. 2020), GoB Lir CasaCeeeBBBaaa Bianchi et al. (2013), CO0P- KerneeUCCDDbbby al. (200)) GP - UCUCCCCodwhnn plementation details are Provided in Appendix F
Gopalan (2017), Pooled LinUCB and Per-User LinUCB, Full im-

---

Published as a conference paper at ICLR 2026
Cunulative regrer
30-
60-
0-
0-
200
400
500
1000
500
1000
1500
2000
0
500
1000
1500 Round
2000
2500
3000
Round
Round
Coop Kenne UCB
GPUCC
GraphucB
LCGPTS
UK-SP-CB
FerUber LinUCB
Pooled: LiniCo
Figure 4: Cumulative Regret under Laplacian-Kereee Kernel regime using representer draw. From left to right tasks of easy level, medium level, hard level.
Environments. We draw a context pool D by sampling from (O, La) first and then normalize the context vectors. round replacement. We generate the user graphs by Ledls--Rénii (ER) random graph model or Radial basis function(RBF) random graph model. After giving the generated graph, we consider one lin- ear regime and two (ernelizec(ponlinear)) regimes for synthetic data simulation. First synthetic data environment called Ginear-GOB. We consider simulating the true graph graph-smooth user pa- rameters + (I + 1,)) - which enforce graph homophily on the random initial parameters O E gn Yang et al. 2020). The homophily strength is controlled by 1) in Linear- Linear-GOB regime. We also generate the true reward functions by simulating multi-user kernel, which is called the Laplacian- Kernel regime. We first use Squared Exponential as our base kernel K₂ over arms UI and construct the multi-user kernel using equation 2 Next, we design two choices to generate f. includ- ing a GP draw and a representer draw. We leave all the details for data simulation in Appendix [.]
present D, by sampling M, distinct items from D without
Task Design. Our experiment has following design of the bandit tasks for a general comparison. In these tasks, the noise of reward is set as a = 0.1 and the number of users is n 20. The simplest level task is 10-arm bandit problem (m 10) with 50% viewability (M, 5) at each round for all users, under T' = 1000 interaction rounds. Medium level task is a 20-arm bandit problem (m = 20) with 25% viewability (M, = 5) at each round for all users, under T 3000 interaction rounds. The hard task is a 50-arm bandit problem (m = 50) with 10% viewability (M₃ = 5) at each round for all users, under T 5000 interaction rounds. In our figures [2] and 4 from left to right are tasks of easy level, medium level, to hard level.
Algorithms Configurations. Our proposals LK--GPUCC. and LK-GP-TS are given in Algorithm and Algorithm 2 in Appendix F.T We implement the hybrid updates using practical recursive up- date in equation and exact update in equation 3 with Cholesky decomposition. Details are in Appendix F4 Hyperparameters and 3 are tuned. For Coop-Kernelune choices of similarity kernel K₂ and conduct an experiment (Figure in Appendix) to verify that the inverse Laplacian L,"' is the optimal choice while the empirical maximum mean discrepancy method is close to the best choice. In the experiment, K₂ is set as the empirical MMD method learn the similarity kernel K₂ unless otherwise stated. The classical baselines for GOB problem, GoB Lin, GraphUCB, and all the remaining baselines, Pool led LinUCB, Per-User LinUCB and GP-UCB, are all UCB-based algorithms. We also tune their hyperparameter for the confidence T bound. The regularization parameter À is is designed as a scheduling A = Abase Sepse T4r where Sype is the ratio of the smallest non-zero eigenvalue to the max eigenvalue and Amsse is tuned. Appendix F5 discusses hyperparameter tuning. All methods run centralized, no-delay setting.
initially set five
Main Findings. Our proposals LK-GP- -P-UCB and LK LK-GP-TS have robust performance in all the 9 data environments. In the Linear-GOB regime, which is the preferred setting for linear bandit algorithms, our proposals can beat the most baselines with clear gaps. In the Laplacian- regime, our proposals are consistently the best choices. For the GP draw setting, our proposals are always the top algorithms in our experiment. For setting using representer draw, LK-GP-UCB and LK GP GP-TS are sublinear while most baselines are hard to achieve sublinear regret. We be- lieve our proposed algorithms can clearly outperform others in long-term manner due to the achievement of the clear sublinear regret. Lastly, even though we conduct an empirical study on the choice for Koop-Kernellu lUCB and pick best one in the comparison, leading to the top per- formances(close to our proposal) of Soop-Kernnell than Coop-Ke rne lUCE.
our LK-GP C-GGPUCC UCB are consistently better
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This material based upon work supported by the National Science Foundation under Award No. 1945667.
REFERENCES
Yasin Abbasi-Yadkorf Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Noga Alon, Nicolo
Claudio Gentile, and Yishay Mansour. From bandits to experts: A tale of domination and independence. Advances in Neural Information Processing Systems, 26, 2013.
Noga Alon, Nicolo
Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, 46(6): 2017.
Mauricio A Alvarez, Lorenzo Rosasco, Neil D Lawrence, et al. Kernels for vector-valued functions: A review. Foundations and Trends@ in Machine Learning. 433):1552266 2012.
Raman Arora, Teodor Vanislavov Marinov, and Mehryar Mohri. Bandits with feedback graphs and switching costs. Advances in Neural Information Processing Systems, 32, 2019.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame-
work for learning from labeled and unlabeled examples. Journal of machine learning research, (11), 2006.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. Advances in Neural Information Processing Systems, 32, 2019.
David Blanco-Mulero, Markus Heinonen, and Ville Kyrki. Evolving gravingg-raphh gaussian processes. arXiv preprint arXiv:21066 10..:22066./177.. 2021.
Sébastien Bubeck, Ronen Eldan, and Yin Tat Lee. Kernel-based methods for bandit convex opti- mization. Journal of the ACM (JACM), 68(4):1 1-35, 2021.
Nicolo Cesa-Biann Bianchi, Claudio Gentile, and Giovanni Zappella. gang of bandits. Advances in neural information processing systems, 26, 2013.
Ronshee Chawla, Daniel Vial, Sanjay Shakkottai, and R Srikant. Collaborative multi-agent hetero- geneous multi-armed bandits. In International Conference on Machine Learning, pp. 4189-4217. PMLR, 2023.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pp. 844-853. PMIR, 2017.
Konstantina Christakopoulou and Arindam Banerjee. Learning to interact with users: A collaborative-bandit approach. In Proceedings of the 2018 SIAM International Conference on Data Mining, pp. 612-622 12-600. SIAM, 2018.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the 2 Annual Conference on Learning Theory (COLT), pp. 355- 366. Omnipress, 2008
Yihan Du, Wei Chen, Yuko Kuroki, and Longbo Huang. Collaborative pure exploration in kernel bandit, arXiv preprint 1rX17:2110.1571,, 2021.
Abhimanyu Dubey et al. Kernel methods for cooperative multi-agent contextual bandits. In Inter-
national Conference Machine Learning, pp. 2740-2750. PMLR, 2020.
Xueping Gong and Jiheng Zhang, Efficient graph bandit learning with obdervvbevvtsonss and switch- ing constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 16871-16879) 2025.
11

---

Published as a conference paper at ICLR 2026
Tomáš Kocäk, Rémi Munos, Branislav Kveton, Shipra Agrawal, and Michal Valko. Spectral bandits. Journal of Machine Learning Research, 21(218): 44, 2020.
Ravi Kumar Kolla, Krishna Jagannathan, and Aditya Gopalan, Collaborative learning of stochastic bandits over a social network. /EEE/ACM Transactions Networking, (6(4):1782-1795 2018.
Vladimir Koltchinskii and Evarist Giné. Random matrix approximation of spectra of integral oper- ators. Bernoulli, 6(1):113-167, 2000.
Andreas Krause and Cheng Ong. Contextual gaussian process bandit optimization. Advances in neural information processing systems, 24, 2011.
Branislav Kveton, Csaba Szepesvari, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic linear bandits. arXiv preprint arXiv:1903.0000 1903.091322. 2019.
Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. On distributed cooperative decision-making in multiarmed bandits. In 2016 European Control Conference (ECC), pp. 243-
248. IEEE, 2016.
Chuanhao Li, Huazheng Wang. Mengdi Wang, and Hongning Wang. Communication efficient dis- tributed learning for kernelized contextual bandits. Advances in Neural Information Processing Systems, 35:19773-19785, 2022.
Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. Proceed- ings of the 39th International ACM SIGIR conference on Research and Development in Informa- tion Retrieval, pp. 539-548, 2016.
Fang Liu, Swapna Buccapatnam, and Ness Shroff. Information directed sampling for stochastic bandits with graph feedback. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018a.
Fang Liu, Zizhan Zheng, and Ness Shroff. Analysis of thompson sampling for graphical bandits without the graphs. arXiv preprint arXiv: 080000000.008930, 2018b.
Shiyin Lu, Yao Hu, and Lijun Zhang. Stochastic bandits with graph feedback in non-stationary environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9758-8766, 2021.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, al. A tutorial on thompson sampling. Foundations and Trends Machine Learning, 11(1): 2018
Alexander J. Smola and Risi Kondor. Kernels and regularization on graphs Computational Learning Theory and Kernel Machines, volume 2777 of Lecture Notes in Computer Science, pp- 144-158. Springer, 2003. doi:
12.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian pro- cess optimization in the bandit setting: No regret and experimental design. arXiv:09/2.3995, 2009.
arXiv preprint
Balazs Szorenyi, Róbert Susa-Fekete, István Hegedus, Róbert Ormándi, Márk Jelasity, and Balázs Kégl. Gossip-based distributed stochastic bandit algorithms. In International conference on machine learning, pp. 19-27. PMLR, 2013.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-29) 1933.
Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pp. 82-90. PMLR, 2021.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv: 2013.
Sharan Vaswani, Mark Schmidt, and Laks Lakshmanan. Horde of bandits using gaussian markov random fields. In Artificial Intelligence and Statistics, pp. 690-699. PMLR, 2017.
12

---

Published as a conference paper at ICLR 2026
Arun Venkitaraman, Saikat Chatterjee, and Peter Handel. Gaussian processes graphs. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5640-5644. IEEE, 2020.
Huazheng Wang, Qingyun Wu, and Hongning Wang. Factorization bandits for interactive recom- mendation. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
Yao Wang, Jiannan Li, Yue Kang, Shanxing Gao, and Zhenxin Xiao. Generalized low-rank matrix contextual bandits with graph information. arXiv preprint arXiv:2507.17528, 2025.
Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual bandits in collabo- rative environment. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pp. 529-538, 2016.
Shuang Wu and Arash A Amini. arXiv:2406. 10686, 2024.
Graph neural thompson sampling.
arXiv preprint
Shuang Wu, Chi-Hua Wang, Yuantong Li, and Guang Cheng. Residual bootstrap exploration for
stochastic linear bandit. In Uncertainty in Artificial Intelligence, pp. 2117-2127. PMLR, 2022.
Kaige Yang. Laura Toni, and Xiaowen Dong. Laplacian- regularized graph bandits: Algorithms and theoretical analysis. In International Conference on Artificial Intelligence and Statisties, pp- 3133-3143, PMLR, 2020.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pp. 17746610756. PMLR, 2020.
Yael Yankelevsky and Michael Elad. Dual graph regularized dictionary learning. IEEE Transactions Signal and Information Processing over Networks, 2(4):61 1 1-624, 2016.
Mengxiao Zhang. Yuheng Zhang, Olga Vrousgou, Haipeng Luo, and Paul Mineiro. Practical con- textual bandits with feedback graphs. Advances in Neural Information Processing Systems, 36: 30592-30617, 2023.
Yin-Cong Zhi, Yin Cheng Ng, and Xiaowen Dong. Gaussian processes on graphs via spectral kernel learning. IEEE Transactions on Signal and Information Processing over Networks, 9:304-314, 2023.
Xingyu Zhou and Bo Ji. On kernelized multi-armed bandits with constraints. Advances in neural information processing systems, 35:14-26, 2022.
A RELATED WORK
Gaussian Processes on Graphs Our kernel construction builds upon foundational work in graph regularization. (Smola & Kondor (003) originally established that penalizing the discrete graph norm If Lf induces a Reproducing Kernel Hilbert Space (RKHS) where the kernel is the pseudoinverse of the Laplacian. Our Theorem 2. formalizes this duality for the vector-valued case via a tensor product RKHS. We note that this structural result can essentially be inferred from the comprehensive review of vector-valued functions by Alvarez et al. Alvarez al. (2012).
Following Smola & Kondor (2003), any positive semi-definite kemne on the vertices that is a func- tion of the Laplacian can be written in the eigenbasis of L as K
Σ r(),) 9:q," where ((Ai, q:) ) are the eigenpairs of L and r(.) 2 O is spectral transfer function. Our choice KG (I) corresponds to r()) 1/(A + p), which monotone decreasing and there- fore shrinks nigh-frequency components more strongly, enforcing smooth/homophiiluss prior. In principle, non mon-moote or band-pass transfer functions r can encode more complex, possibly non- smooth heterophilous relations between users; analyzing such priors in the bandit setting is an interesting direction for future work.
More recent works in graph signal processing adopt related Laplacian-bart constructions but do not use the induced RKHS norm as the main vehicle for analysis. /Vnnitaraman et al. (2020) obtain Gaussian Processes over graphs from Laplacian prior, and Zhi et al. (2023) further generalize
13

---

Published as a conference paper at ICLR 2026
this by learning a spectral filter g( (L) applied directly to the Laplacian. In both cases, the focus is on batch regression and signal reconstruction; the underlying regularizer can be characterized spectrally in terms of the transfer function associated with g. in the sense of [Smola & Kondor (ondor((203), but it is not the primary object of study. By contrast, in our work we commit to the specific Green's s-function the classical Dirichlet energy regularizer and
kernel K (L + p which corresponds enforces a homophilous prior. This choice yields a simple, explicit RKHS norm that we can track throughout the analysis and directly tie the effective dimension and regret in the multi-user bandit setting.
Graph-structure Bandits Graph-based bandit models are also relevant but conceptually distinct. In nonstochastic bandits with graph-structured feedback, a learner chooses an arm (node) and ob- serves the losses of that arm and its neighbors in a feedback graph, interpolating between full- information and standard bandits Alon et al. (2077). Regret bounds in this line of work typically quantities such as the independence number a: (:G)) or related observabil-
scale with graph-theorele ity parameters Alon et al. (2013). Follow-up studies on bandits with feedback graphs and graphical bandits refine these guarantees and extend them to stochastic settings, switching costs, adversarial corruptions, non-stationary environments, and contextual bandits, with regret controlled by parame- ters such as domination and weakkdomination numbers, clique-cover and independence numbers, or maximum acyclic subgraph-type quantities Liu et al. (2][(2018) Sa b): AAror et al. (2019); Lu et al. (202T); Zhang al. 2023). In our setting, the user graph instead encodes prior correlation across user value functions through a Laplacian kernel; feedback remains strietly bandit (we only observe the reward of the chosen user-arm pair). Consequently, the graph enters our analysis only via the spectrum of the user kernel and the resulting effective dimension, rather than via such side-information parame- ters used in graphical bandit regret bounds.
Collaborative Bandits Our approach is related to collaborative contextual bandits on graph, which exploit relations among users to accelerate learning. The collaborative contextual bandit Wu al. 2016) uses a user adjacency graph share context and reward information online, effectively adding a Laplacian-type regularizer to a linear contextual bandit model. Other works consider low- rank or factorization- recommendation Wang et al. (2017) and collaborative filtering bandits that co-cluster users and items in bandit framework [i et al. (2016). complementary line of work studies multi-agen bandits over social networks, where multiple players observe or share each other's 's actions and rewards to reduce regre(Kolla et al.) (2018); Chawla et al. (2023); CChristkkopoulou & Banerjee (2018). These methods typically either (i) impose linear models with manually chosen regularizers, or (ii) model collaboration via latent factors, clustering, or message passing, without an explicit multi-output RKHS/ / GP interpretation. By contrast, our kaplacian-kemnelize construction provides principled kernel view of collaboration: the known user graph defines a positive-definite user kernel that is combined with flexible context kernel, leading algorithms whose uncertainty quantification and regret depend explicitly on the joint spectrum of the graph Laplacian and the base kernel, rather than on the number of users, clusters, or latent dimensions.
collaborative bandits, such as natrrx--fcttrizztton bandits for interactive
Cooperative Multi-Agent Kernelized Bandits Dubey al. (0220) study cooperative multi- agent kernelized contextual bandit with delayed communication over a fixed graph G = (V, F). In their model, every agent v E V acts at every round t, selecting an action Fe,s and receiving a reward yo.s. so that after T rounds there are V 'T' observations; the graph G is used solely to constrain message passing and appears in the regret via graph-theoretic quantities (e.g., clique numbers of graph powers), but it does not enter the construction of the similarity kernel between agents or the modeling of the reward functions themselves. Instead, Dubey et al. posit a latent "network context" 2p for each agent and assume global function F(x, 2) in the RKHS of a product kernel K(xx, 2), (z',,")) = K,(x, Kz
When the network contexts (or the kernel K2) are not available, they propose to estimate them from the contexts 2 by embedding each agent's 's context distribution Pa into the RKHS of K₂ and defining K₂ as an RBF kernel on these mean embeddings. Thus, the agent kernel is ultimately learned similarity over (estimated) context distributions, and the underlying communication graph plays no direct role in defining task similarity or a smoothness penalty on (fr).ev.
By contrast, our setting follows the Gang-of of- Bandits model: at each time step single user is drawn at random, we choose one action for that user, and observe only one reward, that after T
14

---

Published as a conference paper at ICLR 2026
rounds have T observations rather than |V[T. We also behave centralized learner rather than a decentralized network of bandits. Most importantly, we do not introduce or estimate any latent network contexts; instead, assume given user graph and fix the agent kernel to the inverse regularized Laplacian,
(u v) [ Iu.e.
This kernel is tightly coupled to the global homophily penalty on the vector of reward functions and yields explicit RKHS norm with a clear smoothness interpretation. This principled graph-based construction allows us to carry out spectral analysis of the resulting multi-user kernel, relate the regret the spectrum of p, and highlight how the effective dimension adapts the cluster structure of the user graph, rather than reducing network information to ad hoc latent features inferred from context distributions.
B PROOF OF THEOREM 2.
Proof. The proof proceeds in three main steps: (1) We construct the Hilbert space for our multi- problem the tensor product of the user space and the context space; (2) We define feature map into this space and show that its inner product yields the kernel K. This establishes that our constructed space is indeed the RKHS Hi (3) We characterize the elements of H and derive the expression for their norm.
Step 1: Constructing the Hilbert Space via Tensor Product. Let Nr = R" be the finite- dimensional Hilbert space for the users, equipped with the standard Euclidean inner product (u, Uh = u v. {e forms the standard orthonormal basis for Ho. Our multi-user RKHS H the tensor product of HG and Hz:
Hg @ H. RR H...
The elements of H are (limits of) finite linear combinations of elementary tensors of the form 6 h, where E Hy and h E Hz. The inner product in H. is defined on these elementary tensors and extended by linearity:
(u) h1, U2 h2)n == (u1, u2) no (h1, h2)
Step 2: Defining the Feature Map and Verifying the Kernel. Let D /2 be the unique symmetric positive definite square root of Lp- We define the feature map & (4 x D) + H as:
Φ(x,
(I,1/2e) p(x).
This is valid element of since L, product of two such feature mappings in Ht:
1,2 e; R Ho and p(x) Hy. Let's compute the inner
(6(x, (((x))) = ((L, 1/2 e) & p(x). (I, 1/21 e,, p(y))n
(L,1 e, L 1-1/2e ejHHa (p(x)), (1)))
e, L ey K2 (x,
= -L Kz y) K ((x, i), (y.
By the fundamental property of RKHS, since the kernel K is generated by the inner product of the feature map the Hilbert space H. H. is the unique RKHS associated with K.
Step 3: Characterizing Functions in H. and their Norms. An element of H is function f
(U x D) - IR. By the Riesz representation theorem, for each f E H. there exists unique element 0 H such that f(..) (0, ø(-, (((-)))) and |] ||@|| x- For some component functions {gi (g C. H.g we can uniquely express 0 as
ex & 9k
A=
15

---

Published as a conference paper at ICLR 2026
and the squared norm of 0 in H. is then:
n
|001 ex
9k E Ee
Elex eij (gk. g)
Σ
Then relate our reward functions fi:n the component functions f9x 1E=1
f(()) (0, (( i))
E gk. (L (2,) @ p(x))
Σ (ex. 1/2 1='/2ei) (gk: ((
km
1,112 (gk: ((x))
1=1
_ 1/2 (a))(())) (since (0.v()))) - g(x))
k=1
which leads to
9k (x) =
This equality holds for the functions as elements of Hxi 9k = Σラ 11 Jess. 1 Finally, we compute the norm of f in H:
n 19
I1 = 10
l
k=1
n
Σ
/ kg fg
H2
1/2 1g S3 Σ // Juli)..
1/2 kg
[1 1 Jaa (fyr firm.
1/2 kki 11 1k fime.
p
NE
Σ =
where the last step is because the term in parentheses is the (j, ()tth element of the matrix product
1/22 (1 T L. L L, By polarization identity, the associated inner product in H is:
(f = Σ Lolu
16

---

Published as a conference paper at ICLR 2026
To see that I1fl is the exactly the penalty in equation
I expand L, pIn + L:
11
Σ
(pllfi
= 1) (
1.1=1
1 N₂
Σ j1=1
fi)
Using the standard identity for the Laplacian quadratic form, the second term in the above equation is exactly Eis Wisllfi llfi - folli, we get:
11 Σ 1=1
Ifs Is Hew + 5²Σ
way life - 11
i.
This completes the proof.
C PROOFS IN ANALYSIS
We first define following additional notations
b : [0(01, 6(x, u()),,))) uz))
(15)
J. 2. 4;
(16)
r, = J, AT
(17)
Σ. K, + AI,
(18)
Here we have o, xx and J, F3 are from xxxxx
Then we define some useful events for concentration:
E {|2((=)] < / log((2 for all x E D,}
E, (x) + wo. f(x] ue)
where (x) ~ (O0 1) stands for the resampling randomness Thompson Sampling. We also define the confidence round
C. = (1 - f(x,, ui)l s 3r x-1))-((
(19)
where
20
B: = Bp + log + K-,,,
A log
In addition, recall the following effective dimension
log det [TT + KT /\))
d = log(1 + -TKmax/ X)
and the upper bound of the optimality gap:
A S BA = 2B, max
Lastly, we provide the following Lemmas, which are commonly required in regret analysis. Lemma C.1 (Concentrations for TS). For all t E [T'. we have P:(E(() < t- and (((E((CC) 2 (4ev7)=
Lemma C.2 (One Step Regret Bound for TS). Suppose P.(Ef) - Pr(E(() > 0. Then for any t, almost surely,
E, [ATe, I Te, {(EICE) P.(E + +1) Eg Be(z00m.4-102t) + BA P((ET))
where 7t + (io//log((1)))) and Ba 2B, K1/2 max
17

---

Published as a conference paper at ICLR 2026
Lemma C.3 (Cumulative Uncertainty Bound). We have the upper bound for the cumulative esti- mated uncertainty:
Fu.1-1((11) S V 2T max [1, Kmax) log det + X K
Lemma C.4 (Dual Identities), With the defined notations in equation 13
we have two key identities:
E. = + and o ( = (1, u !
C.I
PROOF OF CONFIDENCE SET
Proof of Theorem4.. 4.1 We first decompose
(x) f(x,, u) ke (ar D
0 (.,0 + 6.) - -TTp(ar u)
{ E, ke (x, u)) 0 k: (x,, u) Ex/e, Es 0 (0
(0, (2, u)) (a, u) E.-
bias, (1)20))
noise, (ar
where (x u) D E (x, u) o10, u)
e. Our target is to bound the biasr u) and
noise, (xr, u). We state the following Lemmas:
Lemma C.5 (Bias Identity). The squared bias is the degraded variance for noise:
[16,(2, u) 11,e ,²,,(x)) - (2, u) ", ke(x u) In particular, we have [1,,(z, u)|l S (x)) and Nke (z, u) E, (x u) o,,
(20)
Lemma C.6 (Noise Bound). With high probability, we have the upper bound for the following norm of noise vector Ec:
1 (ee1l1,,' S
Vo2 log log det + + 20 log
From Lemma C
we could bound the bias by bias, (xc, u) ||0| u)ll S Br).,(
(21)
Using the identities above Lemma C.4
we note that
noise, (x, u)
k, u) E, E
olx u) Tr- D.C+ (ó(x, u), D(EE)
S |10( willr, P
(x)((x)
VX |
where the inequality from the Cauchy-Sehwarz inequality for the inner product (:, (r:". Our Lemma C.6 gives the high probability upper bound for the norm || leading to
noise;(x u) < Fu.t
o² log (I, + Ki) + 20 log
(22)
Now combine equation 21 and equation 22 together, have ( f(x, w) < |bias, (xx u) + |noise; u)
/02
1 log det -1KK,) + log 1)
202
Bp + v/=
18

---

Published as a conference paper at ICLR 2026
C.2 PROOF OF REGRET BOUND LK-GP-UCE
Proof of Theorem 4.2 Recall the instantaneous regret at time is A. = s( uz) - sa ue) and
the cumulative regret in time horizon 7 is Rx = Σ A,. We note event C. : { tt (
f(r,, ut)l I 3e- [=x))] happens with high probability (1 - ô), according to Theorem 4.1
Bp + V o²
2x² 1 log
8.
log - + A- 111)) +
(23)
By Theorem 4.1 for all t 2 2 with probability at least - 8,
[(a u+) f( u4)
S Mu,tt (xx) 3e0 (2x f(x,, ut)
$ Mu,t --1 (xx) + m. 1 f( U4)
a,
Thus we have high probability bound for the cumulative regret
T
RT S
2E
3
1 + Bs.
Then we apply Lemma C.3 and the definition of effective dimension in equation I1
Just- (xx)
2T
2T max [1, K max) log det(Ir A KT)
2T max m dlog(1 T> K mmax).
Therefore, we have the final high probability upper bound for regret:
Rr 2E[3rl 2T max Kmax] dlog(1 + TT-- maxx) Ba.
The next step is to analyze the order of the upper bound. By using the effective dimension d again and dropping constants, we have
20 1
3 < B * Rr = O O(dlog(T)TT) Ö(dTT).
dlog(1 + TT-1K mmxx)
max)
log
O(V dllo(T))
X
8
C.3 PROOF REGRET BOUND LK-GP-T3
Proof of Theorem 4.3
We start from the decomposition of the cumulative regret
T
R
Σ EAA = Σ
+ Σ B|A
1=1
t=1
1=1
By Theorem 4.1 and the upper bound for the optimality gap, we know the second term is bounded:
T
Σ
E[A < 8BA
by letting IP.C.) < 8/T for all in Theorem 4.1 For the regret on the event C,, by Lemma
C.2 almost surely, we have
E, A I Ic. (PICE)
- +1) E, Eo/ + Ba Pr(Ett)
2
((
19

---

Published as a conference paper at ICLR 2026
where N/1 Be + Bev log Note that P((E)) - (p())) 2
by
leva
12 20e
Lemma C.1 and the fact that 1² 2 5 for all 2 5. Thus we have
B2 [. S llc.
1944 (0
Bat
by using 40c π + 1 194. Taking summation on both side for our target cumulative regret, we get
[| = E Σ
1=1 <
(194B(/70w,,t-1 + Bat 4Ba]
T
Ee u- (4+ x²²
< 1994
Ba]
6
T
x²
- 1194
0 Ju. (x:) + (4+
6 Bal
where the second equality is using Σi= 2² /6 and the last step is from the monotonicity of the and the nonnegative of ( Our next focus is bounding the summation of uncertainty. As same approach in the proof of Theorem 4.2 we apply Lemma and the definition of effective dimension in equation 11
T
1 (xt) v 27 max {1, K max] log det X- KT)
22T 2T max (1, mmax] dlog(1 TT 111KKam) max).
Thus we have
Σ R[ANTc] S 194l(1r] V 2T max Kmax) d log(1 + TA-1 T Kmax) (4 T²
) )
leading to the high probability (1 - 8) regret upper bound:
π )B + 8BA.
Rr S ( V 27 max K Kmax] dlog(1 + TT- + (4
6
For the order of the upper bound, we first analyze [[Tr], by using the definition of effective dimen- sion again and dropping constants
Pr - + V (2log((TM)) (D,+ + V d log(1 TT-- K Mmx)) +
20
A log
= =()og(TTVV)
where M is the upper bound for the size of action set at time t, i.c. |Dr] < M for all t S T. Therefore,
R = O(d 3/2 Ö(āTT).
D PROOF OF LEMMAS
D. PROOF OF LEMMA
Proof. Using the standard Gaussian tail bound and the classical union bound, we have
(1(((())) u) s
20

---

Published as a conference paper at ICLR 2026
By letting 2 log((t D:l), obtain P,(E()) s t- For the result of event e we have
[127 uz) Ma 1 1207
Pr (uu,t-1(2f))
= P. [x(()))))
(ce)
2 (z(z)( >
2 (4ev
where the first inequality is from the fact that C. holds and the last step is directly obtain by the fact that (ZZ 2 1) 2 (46y7)-1 for NO0 1).
D.2 PROOF OF LEMMA
Proof. This proof is following the classical analysis for Thompson Sampling algorithms Kveton ct al. (2019); Wu et al. (2022): ; Wu & Amini (2024).
We first recall E. = F.). Given randomness from the history F,, event C, becomes deter- ministic and the randomness is only from the resampling step. So have
E,AA.c, Ic. [(
Tc. (E. &y + B.(ATT)))
Tc. IE BA (.T))
where the last step is from the boundness of the optimality gap A, I B3. Our following focus is bounding E, [A indicating C. holds in the remaining part of proof.
We then define the concept of "least uncertain undersampled" action, which is called unsaturated actions, defined
Uc = (x= E Dz: f(xt un) < f(x, u4) + 1 (x))
where
= 3: + 3, 2 (og
and let oe be the least uncertain unsaturated action time t:
c arg min (()).
æElh
Recall the notation for the resampled index is (xx) = Pul 120) + Beza (e On the good situation C, n Et, we have
f(æ, uil ((()) (x) - f(æ u.) S [ia(x)) - 1 + (
Thus we can provide an initial upper bound for regret
A. f(x;; un) - f(x,, uz)
faxj, uz) - fã,,, uz) + f (a, uz) f(x,, uz)
< n- + f(ū,, 4x) - f(x,, uz) + (x((x))) - (xxz) (by ā. E U4)
(24)
2700 + 7o 1- (xt) + pr (x()) (since C. n Et))
2700u.1-1(z) 2 - (by ihe (xx) (e((x)))
Note that
N E Uc) I (
and by taking [:]]]] after multiplying both sides by Tep, we have
( E (4) Et) Ee (2x))
Thus it remains bound the probability Pr(( U4) n ( from below.
21

---

Published as a conference paper at ICLR 2026
We notice the following two facts. First, if [x(x);) > (x) for all Ur then 2; must belong to Ur which means (x;) > maxxel. (e())] C {a+ E U4}. Second, for any æ E Ue on the good situation Ct O & neg, we have
pa(x) S f(x u4) + now,,1112)) S f( us) < pi(x"))
which leads to Ef (ī(();) max [((x))
Therefore, on event C, we have
Pa(far E (E;) 2 Pr((fn(a)))
> max [xxx))())] NE
mtll.
2 Pr NE)))
2 (p()) - ((tt
Now we have upper bound for uu,t- -
E, 1 (x,)
uu.t- 1aat-1(2)) (Tx) -
Pi(la, Ui n (2))
(P(EE) - P. (ET)
which gives the upper bound for instantaneous regret by plugging above result in equation 24
E, B
2 (P - (p,(E))- (
+1) -.(7)0.,.-1
Therefore,
((P(CE) -PP(EE)) + +1) Eg [0 + Ba P((Ett
E, [AA,J. S IIe,
P((()))
D.3 PROOF OF LEMMA
Proof. We first apply Stuchy-Schwartz inequality and obtain
o2
Jo -- (xx) S
T
2 (000)
XT
Tia 1w0s) I 1, which
If X 2 K max, using 0 - (x=s) S |K( uz) (a:e, uz))l S Kmax, we know
leads to
T - (#t)
Σ log 1 + 1 0-)0-1(())) 5
T
2K max
T log 1 - (
<
by applying the fact that 2 log(1 + x)) if 1.
Kmax. still using 0² ( I [K([, (x uz)) S Kmax we know
( S min
Kmax
o --
Kiax min(1, of (
A
which leads to L (20))
K max
Σ min(1 (1, 1 - o (x:1) $ 2K max Σ log 1 1 (zx))
1 2
by applying the fact that min(1, x} < log + x) for 2 0. We can summarize the above two conditions for À together and achieve
Σ 0 d (2:1) t=
2T maaxxf (1 Kmax)
Σ log
1
1 o 1- (2x))
(25)
22

---

Published as a conference paper at ICLR 2026
Now the property of the Shur complement for K₁: det
I Kt
det
I--1 x ((-1)
x
1 +
(((as, Me); (are, uz)) kt B4-1(1m) (2 up) (Kr-1 + XI) -kk (a 24)
which leads to
Σ log [+ on Partt-1aa (2:1)
T
T Σ
deu (I. + x {i))
log
= log dogdot(L) Ly + x Kr).
del (I-1 + x Kx-1)
[=1
Therefore, we combine above result with equation 25 and obtain
Σ 0u.,--1211) S 22 max (1, K log det x (r))
D.4 PROOF OF LEMMA
Proof. We note that
(,e, u)ll (,0((10, u))l E, w) 2(0((xx, u)), ob E (ar, w)h
and we have
|| | E, (xC w)llie = ki u) Σ, 2 E, ki (xx u)
k2 u) E K, (2 u)
ki u) _ E, - ke (2 u)
Nki (x, u) 22, u)
k2 u) T Σ ki (xx u) (2; u) Σ; (2,
and
(ø(( u)), Φ E, ka u)) o((x, u)) Φ E, (x (x, u) T Ex k1( u). Putting above equalities together, we have
[1, 1) = || u))ll - ka, u) T E ki kx u) (x, u) T "m²2ki(a, u.)
K((x, u), u)) k(( u) Ex k) )ki u) T E 2kg kk, u)
(x) Ax, u) T 22, u)
since Σ, is positive semindefinite.
D.5 PROOF OF LEMMA C.6
Proof. We first define
8, D 0(x,, U,
Note that s; is martingale J.,
Also we define a supermartingale
M,(g) erp(
(g. st)
1g 12)
23

---

Published as a conference paper at ICLR 2026
which has alternative form
Mi(g) exp( Σ
(g. Φ ue)le
1 2 [1911²))
where g is the function vector with elements
We follow the approach from classical linear bandit Abbasi-Yadkori et al. (001)) which is averaging Mc(g) w.r. a Gaussian distribution on g. The key technical issue is the infinite dimension of the function vector g. We will first perform the truncated version which can precisely match the classical result. Let d be the dimension of the feature map. Our target the obtain the limiting result when d co. Now assume gd (O, X [a), independent of everything else, and define
M (d) = Eg [M((g") f M fM. (g)
and by iterated expectation (i.e Fubini's theorem). have E[M, (4) [F. M,-1
which shows that M, is supermartingale.
Then we define fa I2d as the truncation projection onto the first d coordinates: 0 [O1. Oa] for any O E e². We further denote
" (aa((1,, u1), ... , Vablar, 4t) E Raxt
and
V.J.V = V.
We notices that
dct(AAa)
det (e V.J.D
det (Id x [.AND
which leads to
Mx(a)
det(ALa)
1/2
cxp
V B 1 ",
det (det(AAa [T)
20
det + -1/2
exp
1
t
20
Let M, be the limit of ((d))
(d) as d + x0, we have
Mt = det [ x0 + +x- 1/2
20 2
1
DrEel(
exp
del [1 + + - 1/2
2 l|
exp 20
where the second step is from (Slyvestr) Weinstein-Arroszajjn identity. By Ville's inequality.
P( sup M, 2 <
E[Ma]
1=0.12,..
and Mo 1.
Thus we know that, with probability at least 8, for 0,1,2,..
1
log(M, S log
which leads to
log (
2 log det (I, [ + 20
1 $
After re-arranging, we get
@eeelle 20 log det Ki)
which shows our result.
24

---

Published as a conference paper at ICLR 2026
D.6 PROOF OF LEMMA C.4
Proof. Let us write D, = U.A.V, V as the singular value (Vcomposition(VVD) of or. We have Ar IA 0] where A is a t diagonal matrix with singular values of o.. We also note that
Σg E Rixt and U₁ E R We also have
A
0
J. -
2. D. V
1
Ve
0
0
and similarly
K, D U,A
Then, we have
T V
A
+
AI
0 No
VJ, E, = U,(A, U +
0
It is clear to have the identity:
Σ, Σ-L D. = =b1;
since both side equal U.! V where D. AI, + AI.) which diagonal matrix.
Next, we note that
(x) = K((x, u), (x, u)) - Ki ( u) Σ, k1 u)
<bx, u) T (1x0 8/ E; 4 (,),
cbx,,)) u) TToo 8. 1. )
which is norm of 6xx, u) induced by matrix
Ixc Φ, T.I.1 = In0 J
(A + Abe)
0 V.
= Vi
Xl
[A A
AV.
V
1
= Ar
Therefore, we have the other identity
(x)) Allo(æ, wll
E MISCELLANEOUS
E.1 ALGORITHMS
Algorithm LK-GP- GP-UCB
1: Input: T, X, (B,17=
2: Initialization; (x)) (w,o(())
3: for 1,.., T do
4: Observe user u, and arm set D..
5: Select arm x;, arg max Mu, (x) + 1,0m,,--((x).
6: Receive feedback Yt = f(x,, u)) + ec.
7: Update (x) and o (x))
8: end for
25

---

Published as a conference paper at ICLR 2026
Algorithm 2 LK GP-TS
Input: T. X. {ve]t=] )T=
2: Initialization: (a..0()), (u,o(a))
3: for 1,.... 7 do
4: Observe user u, and arm set Dr.
5: Sample (z) from N (Pu,,t1 -1,,, for a E Dr
6: Select arm 2; = arg max Pi (z)).
7: Receive feedback Yr = f U1) Ec.
8: Update (a) and o (z).
9: end for
E.2 RECURSIVE UPDATE OF POSTERIOR MEAN AND VARIANCE
This sections refers to the derivation of incremental update of the posterior mean and posterior variance Chowdhury Gopalan (2017), via the properties of Schur complement. Recall that we need to handle the inversion of Σ, I+ AK, Rext which grows with the number of rounds. To compute the inversion of Σg efficiently, we use the recursive formula from E, by block matrix inverse formula
MuL M E,
(26)
M
d;
where
Mi1 = 1111 + + G.
(27)
M = di "1n1 ki= (20 uz)
and
de = K K( ue), (2t, ue)) ki-1 (Rtt Ue) "x-1 k1- (x we) A o2 - + À
G. = -. ( un )k, ( Uz) D,1
Here de is the Schur complement.
Thus have the posterior mean using equation 26
Mu,e
-e u) E, ye (h-- (x, w)
M12 M
y
K ((xx, u), (ate uz))]
M
d.
V1
-,,1 (x, u) 111,191-1 + K((2r, u), (#t,, w4)) M -
+ 1i-1 10-1(xx100 u) 112,131 + K( K( u), (æi, de y/
1 u) ET11 11-1 +d, 1 3331-11 Bsy1 + Ba31)
1hv)e-((a))
where
81 = k 10-1(x110 u) G. = Biyc-1 (k-
, k/ 1 un) 1 (2x
8 = K(xæ, u), (Ii, u4 ki) ui) ΣT B231-1 K((x, u), (xt, us Hu
8. k (z, u) 1r
3, K ((æ, w), (xt, (.)).
Thus have the recursive update of posterior mean
(x)((x)
Ma.t- (x) + d_1
( (x, u) X- kr 1 (xr, us (x)( - ye) + K ((æx, u), (xx, u.) ( Pa,t-1 (12) + dr -- ((x,, w), (ore, (.) M (2xe)
26

---

Published as a conference paper at ICLR 2026
where 9c-1 ((x, u), (xx,, u2)) is defined from 2e (ax, u). (a', u²)) ((x, (2', v²)) - (x. u)
Σ; ke(xx', : vl)
which can be transferred into recursive form using equation 26 de (lo, u), (u))
-K ((,,, w), (z',,')) (k,-1 u) ke
ki- 1 (0', ,²)
d ki 1 (2)) - B2ki-1 (x', ul) - ((0e, wr); (a', w')) + ur), (a', (a', x())) ((-,(( u), (a', , n/)) - di -011(( u), (xt, (r) 1 (10r ue), (x',u')),
Now using the incremental update of the posterior covariance, can easily obtain the recursive update for the posterior variance
(,,( = - (z) d, q ((x, (æz, u4)).
Now replace di by ( À and we achieve the recursive updates in equation 8
F SUPPLEMENT TO EXPERIMENTS
This appendix provides full details of our synthetic environments, algorithm configurations, hyper- parameter selection, implementation choices, ablations, and reporting protocol.
F.1 SYNTHETIC ENVIRONMENTS
Let U [L, [L....,,) n denote users, D C. Rd the arm (context) space, and M; := [Do] the number of candidates shown at round t. We draw global normalized context pool D (xx(1) .......................... (....,,((m)))) ((m)) with (+))) (O(0, Ia) and f. + a / a ()) |]. At round &. we present D, by sampling M, distinet items from 2D without replacement. One user иe is served per round, drawn uniformly from /A unless stated otherwise. Rewards are observed with additive noise y, f(z,, uz) + 6g. We generate graphs, con- texts, and ground-truth rewards under one linear regime (Linear-GOn GOB) and two kernelized regimes (Laplacian- Kernel using GP draw and representer draw).
User graph. We consider two graph random generators on U. First random graph family is Erdōs- Rényi (ER) random graphs: each (undirected) edge is present with probability p and weights wiy = 1. We set p- 0.2 in our experiment. Second one is Radial basis function(RBFF random graphs: sample latent 2, (0, I,), set way exp( (((-ppa pr. z; -,112), and sparsify by keeping edges with We choose = 0.1, PL 0.1 and q = 4 in our simulation.
wiy 2
Task Design. We design different level of the task. The simplest case is (M, My, n, d, T) = (10, 5, 20, 5, 1000). This is 10-arm bandit problem with 50% viewability at each round for all users. The medium level is (M, Mc, n, d) = (20, 5, 20, 10, 3000) which leads to a 20-arm bandit problem with 25% viewability at each round for all users. We also have the toughest (M, n, T) = (50, 5, 20, 20, 3000) which leads to a 50-arm bandit problem with 10% viewa- bility at each round for all users. is set 0.1 unless additional specification.
using
Practical scenarios. Although our empirical study uses synthetic environments, the multi-user, graph-based bandit setting consider is motivated by several practical applications. Examples include recommendation systems, where users are connected via social or similarity graphs and re- peatedly interact with a common catalog of items; regional personalization problems, where stores or geographic areas form a graph and the arms correspond to assortments or pricing actions; and applications in healtheare or education, where patients students are linked through similarity net- works while treatments exercises constitute the arm set. In such domains, the proposed Laplacian kernelized bandits can leverage the user graph to share statistical strength while capturing non-linear context effects.
F.1.1 REGIME Linear-GOR GOB (GRAPH-SMOOTH LINEAR REWARDS)
Sample initial user parameters O, E guxd with rows Oo,: ~ \( Ia). Enforce the graph ho- mophily via Tikhonov smoothing Yankeleesky & Elad (016)):
+
arg min 1 Oo1 + t θ LÔ) = (I, + -
27

---

Published as a conference paper at ICLR 2026
Thus f(x, u) x Ou. where i, is row of θ The strength of the graph homophily 1) is set 1.0 as default.
F.1.2 REGIME 2: Laplacian- Kernell
Our choice of the base kernel K₂ over arms is Squared Exponential which are defined as
(x x') = exp exp((11) (-11o x212
where length-scale > and is set to be 1.0 in our experiment. Then we construct the multi-use -ser kernel by the definition:
K (( u), (a', u')) = | Ju Kz x')
where we set p 0.01 in our experiment.
Option A: Laplacian- Kernel with GP draw
We draw the joint values {f u) weM from the zero-mean GP with covariance induced by K and fix f by interpolation D U. Noise is e, o0) with 0.01 raage(J)-
Option B: Laplacian-Kernel with representer draw We consider the representer theorem for RKHS and sample the i..dd. coefficients via Ozzu -N 1) on D x U and set
f(
Σ
az K ((x, u), (æ', ud)).
E'ED
F.2 BASELINES
All methods face the same sequence {w,: Di, } in each trial of each synthetic environment to ensure fair comparison. Our experiment include the following baselines.
Per-User LinUCB(no graph).: We implement Per-User LinUCB, which ignores the whole graph and perform the linear bandit algorithm independently on each user.
Pooled LinuCB(no graph).: We implement Pooled LinUCB, which ignores graph and person- alization by treating the multi-user problem as a single agent bandit problem. Simply speaking, there is global linear UCB algorithm to solve the problem.
GP-UCB(no graph). We implement GP -ChooChhoyyy & Gopalan (2017), which is the IGP-UCB from the previous study GP and UCB Chowdhury & Gopalan (2017). This is kernelized baseline using K2 on arms only, ignoring the similarities across users (the Laplacian).
GoB.Lin. We implement GoB. Lin, which is the classical methods in gang-og- gang-og-bandits bandits prob- lem Cesa-Bianchi et al.] (2013). This is Laplacian-regularizee linear UCB algorithm on graph- whitened features (equivalent GraphUCB with p i.e A L). The confidence scale in the algorithm is tuned from the table.
GraphUCB. We implement
Yang et al. 2022), the Laplacian-reeullarzed LinUCB. Also, the confidence scale in the algorithm is tuned from the table.
al. (220)), which utilizes the product kernel over agents x arms. Here we borrow the notations from their work. We consider five choices of K; (presented below); the full kernel is K K2 @ K2 and we apply the same UCB rule in LK-GP-UCB.
KOOP-KerEeLUCB. We implement CooP-Kerne Kerne DucE
The five PSD options for the agent kernel K:;
1. laplacian inv: K; (L pT)-1
p> 0.
2. heat: K, exp(-TL) via the spectral decomposition of L.
3. spectral_rbf. embed nodes using the & lowest nontrivial Laplacian eiggaccianeigeevectooo 2 E Bank and set
K2 K2(u, w/] = exp
12.. 12m.-2,1 2,, 20²
28

---

Published as a conference paper at ICLR 2026
4. all ones: full cooperation, K; = 11
5. learned mmn (network contexts, faithful to Dubey et al. (2020)): define per-user kernel mean embeddings V, of the observed arm-context distribution in Has and let
(,,( =exp
[1)., (01l
20
where (1) is the empirical mean embedding of contexts observed for up time t. In our implementation we use an efficient random Fourier feature approximation for K₂ and update gt on fixed schedule; users with fewer than small threshold of observations cooperate only with themselves (diagonal entries).
For time-varying K2 (learned_mmil the GP state is rebuilt at K2 refresh points using the algo- rithm's 's own history, ensuring consisteney of the Gram matrix with the current kernel. Flgure shows the comparison the choice of Kg for COOP KernelUCB.
700
Coop: Kernelici (all ones)
600
KernelUcB (heat)
(espaacen_jnv)
Cumulative Regres-
Coop KamelUce (eaaeed mmdd
Coup Kepp-KemeeUBBB (spectre__ff
400
200
200
400
600
800
1000
Round
Figure 5: Comparison of the choice of user-similarity kernel for -eee-KKnneeelll
F.3 CENTRALIZED PROTOCOL
At each I: sample u, ~ Unif(l4), present 'D (size Mr), select æt, E Dr per the algorithm, observe yr. update our decision policy(model). and record A, max f(x we) f( (()),.)) Each configuration is repeated for R trials (final results use R = 20; preliminary/pilot tuning uses R e [5, 10).
F,4 POSTERIOR UPDATES AND NUMERICAL DETAILS
Motivation. For the original update equation at round f, the inversion takes O(t)ID,)) time. The practical updates is efficient for each pair (x, u) while it requires the updates for all pairs, leading to ((D,, |n) time. Therefore, high-level idea is to perform original updates equation 3 when t < 4/ and perform practical updates equation & when when & < 1/3 Therefore, for GP- based methods we use hybrid implementation, which is described as below.
Exact (Cholesky) phase: maintain Σ, K, XJ and update via rank-one Cholesky for L L. (cost ((12) per step; initial inversion (())))
Recursive phase: switch to the rank-one recursions in equation & with go K restricted D U. This costs (nl (Pl)) per update when applied to the whole grid D x U.
By default we take 4, 1100, [n as the phase switch. We use Cholesky jitter 10-8 clip negative variances zero, and cache (D, D). For large we optionally apply graph spectral truncation L, 2 U.T. (top-r eigenpairs), yielding zo (U,A, "U 8 K
F.5 HYPERPARAMETERS AND TUNING
What is fixed across algorithms. For fairness, base-kernel hyperparameters are fixed inside each environment: the length-scar scale uses the median heuristic on D, and the Laplacian ridge p 0.1 is fixed. For Kg, laplacian inv uses = 0.1; heat uses 7 = 1.0; spectral rbf uses = and median bandwidth; learned mmnd uses random-feature dimension 256, median bandwidth heuristic, update
29

---

Published as a conference paper at ICLR 2026
interval around 200 rounds, and minimum count of observations before participates in cooperation.
What is design. To avoid using unknown noise scale as prior, all GP-style methods graph- and time-aware ridge schedule
T T +
(L)
d
Abase
Seper
Saper
E [0,1] 1], L)
mmax
where AFiedter (L) is the Fiedler value (smallest non-zero eigenvalue). We clip X to Amins Amax with Amin = 10-6 and Amax 10-1 To limit refactorizations, we update À doubling epoch schedule (approximately at t= 200, 400, 800,...) and only rebuild if the change exceeds 20%.
What is tuned. Only the exploration scales tuned by grid search on a pilot horizon (Tpito 1500 for medium/hard; pioe = 1000 for simple) using Rpilot E {5, 10}:
Algorithm
Grid (pilot)
LK-GP-UCB, GP-UCB, Coop-
B (0.5, 1,2,4)
LK-GP-TS
E (0.5, 1]
Lin, GraphUC3, LinUCB variants
E {0.5, 1, 1,
The best pilot setting (by mean pilot cumulative regret) is frozen for the full-horizon evaluation. Noise/ridge \base in GP updates uses Xbase {0.001, 0.005, 0.01, 0.05, 0.1} on the pilot.
F.6 ABLATIONS AND STRESS TESTS
We report two ablation studies. One is an ablation under the medium, Laplacian- Kernel with GP Draw environment (ER graph, fixed l and p) on Scalability in users (n): n E {20, 50, 100, 2003 with fixed (M, M2, d, T) and graph generator. We provide the final cumulative regret vs. n report the last step cumulative regret in Table Another study is on the effect of random graph models. Our standard experiment uses two graph random generators: Erdös-Rényi (ER) random graphs and the Radial basis function(RBI)) random graphs, mentioned in F. We add the stochastic block Models(SBM) in this ablation study. We still keep the medium, Laplacian Baalaciin-KKenell with GP Draw environment. The result is shown Figure
Table 1: Ablation over number of users n (final cumulative regret; m SSB).
Algorithm
= 20
n 50
n - 100
n 200
LK-GP-UCB
627.22 + 32.98
892.43 + 21.73
1062.69 + 18 29
1157.74 +: 23.02
LK-GP-TS
634.46 22.78
943.41 + 19.56
1176.23
15.77
1260.35 + 16.23
CoD
730.06 + 31.02
1015.35 + 22.18
1273.28 + 17.36
1358.48 + 14.22
GOB.Lin
1092.86 71.70
1203.32 = 18.57
1370.51 16.78
1432.48 + 18.72
GraphUCB
1105.20 + 68.54
1192.30 = 22.12
1360.02 + 15.32
1453.21 + 17.81
GP-UCB
2222.20 + 90.26
1964.65 = 61.40
1641.43 37.43
1444.83 1 36.33
Pooled-LinUCB
2360.95 + 70.55
1909.81 = 49.49
1723.27 + 40.23
1438.74 788.77455 + 26.44
PerUser-LinUUB
1117.87 + 72.04
1221.99 = 22.03
1432.89 18.81
1527.04 + 17.61
Algorthen
Cunulative
Round
Round
Round
Figure 6: Comparison the choice of random graph models.
30


Reviews:
[{"review_id": "8BcD7p7CNS", "reviewer": "Reviewer_jACQ", "summary": "This paper addresses the problem of multi-user contextual bandits and proposed a framework based on a novel penalty that explicitly captures the relations between the user reward functions. The authors went on to provide a justification of this penalty by linking it to a multi-user RKHS, which allows for the development of two Gaussian process based algorithms. Theoretical result on  the regret bound has been derived for both algorithms, and experimental results validate their  effectiveness and superiority over existing baselines.", "questions": "See weaknesses above for the specific points I would like the authors to address or discuss.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper tackles an under-explored but interesting problem.\n- The formulation of the penalty and its link to a RKHS is interesting and provides guidance on how relational information can be taken into account in learning.\n- Theoretical results on regret bounds are a plus.\n- The paper is generally well presented with clear motivation and technical descriptions.", "weaknesses": "**Connection to existing literature.** I believe it would be helpful for the authors to make a greater effort connecting their approach to similar attempts in the literature:\n- First, the link between kernels and regularisations, as well as its extension to the graph case via the graph Laplacian, has been well-documented in the literature [1], and in my view this should be properly discussed in the derivation of the proposed approach.\n- Second, the way the graph structure is incorporated into learning bears similarly with recent work in the space of multi-output and graph-based GPs, where this is done either implicitly [2] or explicitly [3,4]. I feel additional discussion and comparison against those would make the contribution of the paper conceptually clearer. \n\n**Technical framework.** The paper only focuses on a smoothness assumption, which is a reasonable starting point, however I was left wondering whether this can be generalised to the case where the user reward relations are more complex? I feel this should be possible to address by following for example the spectral learning approach in [4]. \n\n**Experiments.** Experimental results, while convincing, are relatively brief:\n- Can the authors demonstrate the impact of different graph topology on learning performance, for example by using graphs generated from the stochastic block model? I think this can connect nicely to the discussion on effective dimension. \n- Can the authors provide ablation studies that demonstrate the utility of both the graph-based kernel and the classical kernel in the Kronecker product? \n- All experiments are synthetic at the moment, can the authors think about potential real-world experiments? This can also help a reader appreciate the practical utility of the proposed approach.\n\n[1] Smola and Kondor, “Kernels and Regularization on Graphs,” COLT, 2023.\n\n[2] Alvarez et al., “Kernels for vector-valued functions: A review,” Foundations and Trends in Machine Learning, 2012.\n\n[3] Venkitaraman et al., “Gaussian processes over graphs,” IEEE ICASSP, 2020.\n\n[4] Zhi et al., “Gaussian Processes on Graphs Via Spectral Kernel Learning,” IEEE TSIPN, 2023.", "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": "", "extra_scores": {}}, {"review_id": "rCF6ugHuU9", "reviewer": "Reviewer_xoe9", "summary": "This paper studies multi-user contextual bandits with a known user graph. The authors show how individual RKHS-based reward modeling and graph homophily (via the graph Laplacian) come together by deriving the reproducing kernel of a unified multi-user RKHS. Using this kernel, they design GP-UCB and Thompson Sampling algorithms and analyze their regret.", "questions": "I am a bit surprised by the reported TS result. With a naive TS design, the paper claims a frequentist regret of order $d\\sqrt{T}$. However, up to my knowledge, even in the simpler linear bandit setting, the naive version of TS typically achieves only $d^{3/2}\\sqrt{T}$ frequentist regret, and stronger results usually require additional design modifications such as the feel-good TS algorithm [1]. Could the authors clarify what differs in their analysis that allows this improved bound? Or are there extra assumptions that effectively bypass the limitations known in previous TS literature?\n\n\n\n[1] Zhang, Tong. \"Feel-good thompson sampling for contextual bandits and reinforcement learning.\" SIAM Journal on Mathematics of Data Science 4.2 (2022): 834-857.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. Theorem 2.1 provides a clean theoretical connection between Laplacian regularization across users and RKHS-based regularization on arm features. This connection is elegant and makes the overall framework principled and well-founded.\n\n2. The proposed GP-based UCB algorithm are grounded on solid theoretical foundations. The corresponding regret bounds based on the effective dimension are sharp and well-justified, making the theoretical contribution of the paper clear and convincing.", "weaknesses": "1. The formulation mainly builds on previous work on linear Laplacian bandits by extending the idea from linear models to general RKHS functions. While the conceptual novelty is moderate, I think this extension is meaningful and technically non-trivial, as it requires re-deriving the RKHS characterization and associated regret analysis.\n\n\n2. I am a bit confuse about the result for TS, as described below in detail.", "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": "", "extra_scores": {}}, {"review_id": "fqHFZlDXnv", "reviewer": "Reviewer_ZSey", "summary": "**Summary**\n\nThis paper addresses the multi-user contextual bandit problem where users are related by a graph and reward functions are both non-linear and exhibit graph homophily (i.e., connected users have similar rewards). The authors introduce a joint penalty that combines a graph smoothness term (based on RKHS distances between users) with an individual roughness penalty for each user's function. The central contribution is a proof that this intuitive, additive penalty is mathematically equivalent to the squared norm within a single, unified multi-user RKHS. The authors explicitly derive the reproducing kernel for this new space, which fuses the graph Laplacian and the base arm kernel. This unification allows them to reframe the problem as learning a single \"lifted\" function, enabling the development of GP-based algorithms. They provide regret bounds that depend on the effective dimension of this new kernel, rather than on the number of users or ambient dimension, and show empirically that their methods outperform strong baselines in non-linear settings.\n\n\n\n\n**Advantages**\n\n* The theoretical unification of the graph smoothness penalty and the individual RKHS penalties into a single, valid multi-user RKHS is the strength of this paper, providing a foundation for the proposed algorithms.\n\n* By deriving the explicit multi-user kernel, the paper bridges the gap between Laplacian regularization and kernelized bandits, allowing the direct application of powerful GP bandit machinery (UCB and TS) to the graph-based problem.\n\n* The resulting regret bounds replace a direct dependency on the number of users ($n$) with a dependency on the \"effective dimension\" of the new kernel, which captures the spectral properties of both the graph and the arm kernel.\n\n\n\n\n**Shortcoming and Questions**\n\n* The practical implementation of the proposed algorithms requires inverting a $t \\times t$ matrix at each step $t$, leading to a computational complexity that scales poorly with the number of rounds, a common issue for GP-based methods.Given that the paper suggests recursive updates as a solution, could the authors provide an experiment comparing the cumulative regret of the exact GP-UCB update versus a more scalable approximation (like the recursive formulas or a sparse GP approach) as the time horizon $T$ becomes very large?\n\n\n* The derived kernel requires the inversion of the $n \\times n$ regularized Laplacian $L_{\\rho}$, which could be computationally prohibitive if the number of users ($n$) is extremely large (e.g., millions of users). Would it be possible to conduct an experiment analyzing the scalability of the method with respect to the number of users $n$, and perhaps explore whether an approximation of $L_{\\rho}^{-1}$ (e.g., using graph sparsification or spectral methods) could maintain competitive regret?\n\n\n* The theoretical regret bounds depend on the effective dimension $\\tilde{d}$, which is data-dependent and defined based on the entire sequence of actions up to time $T$, making it an a-posteriori quantity that is not known in advance. Could the authors provide an empirical analysis plotting the growth of the effective dimension $\\tilde{d}$ relative to $T$ in the synthetic experiments, to give a clearer intuition for how this value behaves in practice?", "questions": "Please see above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Please see above.", "weaknesses": "Please see above.", "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": "", "extra_scores": {}}, {"review_id": "LhpH7eA29J", "reviewer": "Reviewer_uAXP", "summary": "The paper studies multi-user contextual bandits where users are connected by a known graph and have nonlinear reward functions. It builds a joint RKHS kernel combining (i) graph smoothness via the Laplacian and (ii) nonlinear structure over arms, and then runs GP-UCB / GP-TS on this kernel. It proves regret bounds that depend on an effective dimension of the graph+kernel, not just number of users, and shows strong performance in experiments.", "questions": "See weakness.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Gives a clean unified kernel that fuses graph structure and nonlinear rewards in one theory.\n- Provides GP-UCB / GP-TS algorithms that share information across similar users automatically.\n- Regret scales with an effective dimension (can be much smaller than #users).\n- Shows consistent empirical gains, especially on nonlinear graph-smooth tasks.", "weaknesses": "- The paper omits key related work. The problem setting is very close to prior work on graph-structured / collaborative contextual bandits [1][2], but these are not adequately discussed in the introduction or positioned against the proposed approach.\n\n- The baseline comparison is incomplete. Modern neural contextual bandits can learn richer representations than fixed kernels, e.g. neural GP / neural UCB style methods [3]. These should be discussed and, ideally, included as baselines.\n\n- The UCB/TS exploration terms depend on problem-dependent quantities (like the RKHS norm bound and noise level). These are not observable in practice, so the theoretical guarantees rely on tuning parameters you don’t actually know.\n\n- While the bound is written in terms of an “effective dimension” $\\tilde{d}$, the asymptotic rate is the same $\\sqrt{T}$ scaling as standard kernelized bandits. The paper does not prove matching lower bounds or show regimes where $\\tilde{d}$ is provably small, so the improvement can be marginal.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)