Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces Joyanta Jyoti Mondal1∗ , Ibne Farabi Shihab2∗† , Anuj Sharma3 1
arXiv:2606.27917v1 [cs.LG] 26 Jun 2026
Department of Computer and Information Sciences, University of Delaware, USA 2 Department of Computer Science, Iowa State University, USA 3 Department of Civil, Construction & Environmental Engineering, Iowa State University, USA [email protected], {ishihab, anujs}@iastate.edu Abstract Contextual bandits with graph-structured arms arise in recommendation, citation retrieval, and social advertising, where arms connected on a graph tend to share reward signal. Standard dimensionality reduction ignores this structure, inflating exploration cost by a factor of d/k. We propose GraphDRLinUCB, which projects arm features onto the graph’s lowfrequency spectral subspace and runs linear UCB in √the resulte T ) regret ing k-dimensional space. We prove the first O(k bound for spectral-projection-based contextual bandits, reducing dimension dependence from d to k; a perturbation argument extends this to noisy graphs, with an explicit penalty for reward-smoothness mismatch and graph-estimation error. Our central theoretical finding is that the high-frequency reward component need not incur a worst-case linear-in-T penalty: its actual cost depends on its realized impact along the played path, not on its total energy. A simple spectral comparison between subspaces (Γk ) predicts which reducer wins on a given dataset, correctly calling five of six real-dataset outcomes without any fitted threshold. Across a synthetic benchmark and six real datasets (MovieLens, Amazon, LastFM, ogbnarxiv, MIND), GraphDR-LinUCB reduces cumulative regret by 15× over full-dimensional LinUCB and outperforms competing graph-aware methods on five of six; the single failure is precisely where the graph’s spectral subspace is misaligned with the reward.
Introduction Contextual bandits with graph-structured arms appear broadly in deployed systems [25]; users connected by social links, products organized by co-purchase or genre, and documents linked by citation. In each setting, reward functions are typically smooth over the graph (nearby nodes share expected reward), and graph spectral methods are designed precisely to capture this structure. The natural question is whether projecting arm features onto a low-frequency Laplacian eigenspace, reducing the exploration dimension from d to k ≪ d, can deliver a genuine regret improvement over operating in the full feature space. ∗
These authors contributed equally. Corresponding author. Copyright © 2027, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. †
The answer is not obvious. Standard misspecified-linearbandit theory [24, 12] charges a worst-case bias proportional to νk T for any deviation of the reward from √ the projected subspace, which can quickly dominate the T exploration gain. Prior graph-bandit work sidesteps this by either propagating information along edges [13, 5] or soft-regularizing with the graph Laplacian [38]; neither performs a hard projection that actually reduces the exploration dimension. Spectral bandits [34] operate in a graph-frequency basis but do not analyze noisy eigenspaces or quantify the cost of imperfect graph smoothness. The theoretical viability of hard graph-spectral projection for bandits, and its practical conditions, remain uncharacterized. Moreover, a hard projection is useful only when the reward is smooth on the graph (a property of the data, not the algorithm), making a structural falsification test essential: projecting onto a node-permuted eigenspace leaves the dimension unchanged but destroys graph-reward alignment, so any genuine gain must collapse. To tackle these challenges, we study GraphDR-LinUCB (graph dimensionality reduction): project each arm’s feature vector onto the bottom-k Laplacian eigenspace and run LinUCB [1, 3] in the resulting k-dimensional space, with graph-shuffle controls on every experiment as a structural falsification test. We prove exact-subspace and Davis–Kahan robust regret bounds, develop a structure-specific residual analysis that replaces the worst-case misspecification penalty with realized graph quantities, and introduce a spectral selection rule for choosing between graph-DR and competing reducers without fitting any threshold. Contributions. • Finite-sample and robust bounds. We prove that √ e T ) regret under exGraphDR-LinUCB achieves O(k act graph smoothness, reducing dimension dependence from d to k. A Davis–Kahan argument extends this to approximate smoothness and noisy graph observation, making the regret cost of eigenspace estimation error explicit through the spectral gap ∆k and smoothness tail ζk . • Structure-specific residual theorem. We show that the high-frequency residual need not be paid for at the worstcase linear-in-T rate. The cost is governed by two realized
graph quantities, residual leverage SRLT and candidateset residual width CRWT , which are sublinear when the residual is graph-benign. An implementable pilot-based variant makes this bound computable from data. • Spectral selection rule. We define the subspace-capture 2 2 margin Γk = Uk⊤ θ 2 − P ⊤ θ 2 , a zero-parameter spectral statistic that predicts which reducer better aligns with the reward without requiring any fitted threshold. We evaluate it alongside the theory-derived diagnostic Gk and the scalar tail ζk . • Empirical evaluation. We validate the approach on stochastic block model and random-geometric-graph synthetics with graph-shuffle controls on every configuration, and evaluate on six real graph-bandit datasets spanning recommendation, news, and citation (MovieLens100k/1M, Amazon, LastFM, MIND-small, ogbn-arxiv).
Related Work Linear contextual √ bandits. The LinUCB framework [7, 3, e 1] achieves O(d T ) regret for d-dimensional linear rewards through elliptical confidence sets and self-normalized mar√ tingale concentration [23], with a matching Ω(d T ) lower bound established by Dani et al. [9]. Beyond UCB, Thompson sampling [6, 32] provides a Bayesian alternative exploration strategy. Misspecified linear bandits. When the reward is only approximately linear in the chosen features, regret incurs an additional bias term. Worst-case analyses [24, 12] pay an envelope that is linear in the horizon and proportional to√the misspecification level, a cost that quickly dominates the T exploration term even under mild misspecification. Sharp horizon-dependent analyses of KL-regularized contextual bandits [40] sharpen these worst-case envelopes under regularization, though the graph-structural form of the residual remains unexamined. Graph bandits. Online clustering of bandits [13] propagates reward information across a user graph by sharing estimates between neighboring arms. Laplacian-regularized LinUCB [38] adds a graph-smoothness penalty to the ridge objective, biasing the estimator toward functions that vary slowly over the graph. The graph-feedback bandit setting of Mannor and Shamir [26] observes neighboring arm rewards as side information; recent work extends this to similar-arm graphs [30, 17] and interference structures [18]. Wang et al. [36] combine low-rank structure and graph Laplacian regularization for matrix contextual bandits via soft penalization; the present paper instead uses hard spectral projection and derives an explicit spectral-gap regret bound. Spectral bandits. Spectral bandits [34] design algorithms for payoffs that are smooth functions on a graph, with regret governed by a spectral effective dimension that reflects the concentration of the payoff in low-frequency graph coordinates. The algorithm operates in the full graph-frequency basis with a per-eigenvalue smoothness weight rather than a hard truncation at a fixed dimension k.
Graph signal processing and spectral embeddings. Laplacian eigenvectors as low-frequency graph coordinates originate in graph signal processing [33] and underpin Laplacian Eigenmaps [4] and spectral clustering [27, 35]. Our contribution is not a new embedding method but the first bandit regret analysis tying hard spectral projection to exploration cost. Model selection and adaptive k. Corralling methods [2] achieve regret competitive with the best algorithm in a pool of base learners, and model selection for contextual bandits more broadly has been studied via smoothed meta-algorithms [28], providing a plausible path to adaptive-k GraphDR; a tight graph-specific theorem is left to future work. Dimension reduction in bandits. Random projection [39] reduces the feature dimension before running a linear bandit, with regret depending on the projected dimension. Bilinear bandits [20] exploit low-rank reward structure via a two-stage √ subspace-exploration approach achieving e 1 +d2 )3/2 rT ) regret, and tight two-to-infinity subO((d space recovery methods [19] sharpen these bounds for matrix bandits. Recent work handles non-stationary subspaces: √ e T ) dynamic regret for Khosravi and Huo [21] prove O(r piecewise-stationary low-rank linear bandits, and Dai et al. [8] attain rank-dependent regret for adversarial contextual bandits with low-rank experts in a model-routing setting. Beyond subspace methods, matrix sketching for highdimensional linear bandits [37] shows adaptive sketch sizing is needed to avoid linear regret under heavy spectral tails. In multi-agent and distributed settings, the spectral gap of the communication graph directly controls the regret of cooperative bandit algorithms [29, 31]. None of the above uses a graph-structural subspace as the feature projector or ties bandit regret to the reward-graph spectral gap. The present paper provides the first such analysis, characterizing when projecting arm features onto the Laplacian eigenspace reduces exploration cost and when it does not.
Setup and Algorithm Graph and Laplacian. Let G be an undirected graph with symmetric normalized Laplacian L = I − D−1/2 AD−1/2 , whose eigenvalues satisfy 0 = λ1 ≤ λ2 ≤ · · · ≤ λn ≤ 2. We assume nonnegative edge weights and no isolated nodes, adding self-loops where needed so that Dii > 0. We further assume a positive separating eigengap ∆k = λk+1 −λk > 0, so that the bottom-k eigenspace is well defined. Let Ek ∈ Rd×k be an orthonormal basis for the feature-space lowfrequency subspace, with projector Πk = Ek Ek⊤ . In the node-arm, one-hot-feature case, d = n and Ek = Uk , where Uk collects the k lowest-frequency Laplacian eigenvectors. Throughout the theory, Uk includes the constant eigenvector u1 (λ1 = 0 on connected graphs); experiments shift to u2 , . . . , uk+1 and report that convention explicitly. The analysis is for the node-arm setting d = n, xt,a = ea , Ek = Uk . Bandit interaction. At each round t, the learner observes a finite arm set At , where arm a ∈ At has feature xt,a ∈ Rd .
Algorithm 1: GraphDR-LinUCB b arm-feature oracle xt,a ; diInput: Observed Laplacian L; mension k; regularization λ > 0; confidence sequence (βt )t≥1 Output: Pulled arms a1 , . . . , aT bk ∈ Rd×k 1: Compute bottom-k orthonormal eigenbasis E b of L. 2: Initialize V1 ← λIk , b1 ← 0 ∈ Rk . 3: for t = 1, 2, . . . , T do 4: Compute α bt ← Vt−1 bt . 5: Observe candidate set At ; project each arm: zt,a ← b ⊤ xt,a for all a ∈ At . E k h i Pull at ← arg maxa∈At
⊤ zt,a α bt + βt ∥zt,a ∥V −1 t
7: Observe reward yt . ⊤ 8: Vt+1 ← Vt + zt,at zt,a ; t 9: end for
bt+1 ← bt + zt,at yt .
6:
.
⋆ After choosing at , it receives reward yt = x⊤ t,at θ +ηt , where θ⋆ ∈ Rd is unknown and ηt is conditionally sub-Gaussian noise. In practice, the clean Laplacian may be unavailable. b denote an observed or estimated Laplacian and E bk ∈ We let L Rd×k an orthonormal basis for its bottom-k eigenspace, and bk = E bk E b ⊤ and Pb = E b ⊤ . The projected feature is set Π k k ⊤ k b zt,a = Ek xt,a ∈ R .
Algorithm. GraphDR-LinUCB (Algorithm 1; pipeline in Figure 1) runs ordinary linear UCB in the k-dimensional projected space; the projection Pb is the only thing that distinguishes it from standard LinUCB.
Regime
Assumption ⋆
θ ∈ range(Πk ), known Ek tail ∥rk ∥ ≤ ζk , b−L ≤ L εL realized trajectory
Exact subspace (Thm. 1) Generic robust (Thm. 4)
Structurespecific oracle (Thm. 5) Estimated residual (Thm. 7)
Regret guarantee √ e O(k T ), dimension d → k √ ek T O + Lx (ζk + Sk εL /∆k ) kT (linear bias) ≤ 2βT0 +1 AT + 2SRLT AT + CRWT
e r kT ); implepilot rb, oracle bound + O(e ∥b r − r⊥,k ∥ ≤ mentable er
Table 1: Summary of the four theoretical regimes. The structure-specific bound (Thm. 5) tightens the generic worstcase linear bias to realized graph quantities SRLT and CRWT (Corollary 9); the estimated-residual variant (Thm. 7) makes it implementable.
Define pseudo-regret PT ⋆ ⋆ ⊤ Reg(T ) = t=1 maxa∈At x⊤ t,a θ − xt,at θ . Theorem 1 (Reduced-dimension regret under exact smoothness). Under Assumptions 1 and 2, suppose the algorithm uses the true projection Ek⊤ , regularization λ ≥ L2x , and confidence radius r √ (t−1)L2 βt = R k log 1 + λk x + 2 log 1δ + λS.
We present three theorems in order of increasing sharpness. Table 1 summarizes all three regimes; proofs are in the appendix section.
Then, with probability at least 1 − δ, simultaneously for all T ≥ 1, r T L2 Reg(T ) ≤ 2βT +1 2T k log 1 + λkx .
Exact known-subspace bound
√ e Consequently, for fixed R, Lx , S, λ, δ, Reg(T ) = O(k T ).
When the reward is perfectly smooth on the graph, projection onto the Laplacian eigenspace is lossless and the problem reduces exactly to a k-dimensional linear bandit. Assumption 1 (Exact graph smoothness). There exists α⋆ ∈ Rk such that θ⋆ = Ek α⋆ . Equivalently, θ⋆ ∈ range(Πk ). Under Assumption 1, zt,a = Ek⊤ xt,a satisfies
Corollary 2 (Comparison with full-dimensional √ LinUCB). e Full-dimensional LinUCB in Rd has rate O(d T ). Under exact graph smoothness and k ≪ d, GraphDR-LinUCB reduces the dimension dependence from d to k.
⋆ ⊤ ⋆ ⊤ ⊤ ⋆ ⊤ ⋆ x⊤ t,a θ = xt,a Ek α = (Ek xt,a ) α = zt,a α ,
In practice, two idealizations of Theorem 1 fail simultaneously: the reward may carry energy outside the first k graph frequencies (ζk > 0), and the eigenspace is estimated from a noisy Laplacian (εL > 0). The following handles both. The key tool is a projector-perturbation bound from Davis and Kahan.
Theory
so the projected problem is an exact k-dimensional linear bandit and the standard LinUCB analysis applies verbatim in Rk . Assumption 2 (Bandit regularity). For all t and a ∈ At , ∥zt,a ∥2 ≤ Lx . The projected parameter satisfies ∥α⋆ ∥2 ≤ S. The noise sequence is conditionally R-sub-Gaussian with respect to the filtration Ft generated by the history before observing yt : E[exp(sηt ) | Ft ] ≤ exp(s2 R2 /2) for every s ∈ R. The arm sets and features may be chosen adaptively from the past but are fixed before ηt is realized.
Robust gap-dependent bound
Lemma 3 (Davis–Kahan projector perturbation [10]). Asb are symmetric and L b−L sume L and L ≤ εL ≤ 2
∆k /4. Then b k )Πk (I − Π
b k − Πk Π 2
2
≤ 4εL /∆k , and consequently
≤ 4εL /∆k .
Laplacian L bk basis E
Graph G
project bk⊤ x z=E
LinUCB in Rk
pull at
b k )θ⋆ residual r⊥,k = (I − Π controls SRLT , CRWT
bk ; arm features are Figure 1: GraphDR-LinUCB. The graph determines a bottom-k low-frequency Laplacian eigenbasis E k projected to R and LinUCB runs there. Only the high-frequency residual r⊥,k left outside the subspace can hurt the learner; its effect is governed by the realized graph quantities SRLT and CRWT . The shuffle control permutes node labels before computing bk , preserving the projected dimension but destroying graph alignment and eliminating the regret advantage. E Assumption 3 (Approximate smoothness and noisy graph). Let rk = (I − Πk )θ⋆ . Assume ∥Πk θ⋆ ∥2 ≤ Sk and ∥rk ∥2 ≤ ζk . The ambient features satisfy ∥xt,a ∥2 ≤ Lx for all t, a. The noise is conditionally R-sub-Gaussian as in Assumption 2, and the arm sets are chosen before the current noise is realized. Theorem 4 (Generic robust regret bound). Assume Lemma 3 and Assumption 3. Run GraphDR-LinUCB with Pb = b ⊤ and λ ≥ L2x , with confidence radius βt = βt0 + E kp νk 2(t − 1)k log(1 + (t − 1)L2x /(λk)) (equivalently βt0 + νk AT for known horizon T ), which requires νk known or upper-bounded. Define γk =
Main result: structure-specific residual regret The generic bound of Theorem 4 uses only the scalar envelope |ξt,a | ≤ νk , treating the high-frequency residual b k )θ⋆ as an arbitrary adversary. In graph problems (I − Π this residual is not arbitrary: it is a high-frequency graph signal, and it harms the learner only through the arms that actually appear and the low-frequency coordinates that are actually played. The following theorem retains this structure instead of collapsing it into νk . b k )θ⋆ and ξt (a) = x⊤ r⊥,k . Let r⊥,k = (I − Π t,a Definition 1 (Residual leverage and candidate residual width). For a realized trajectory, define the residual leverage Pt−1 SRLT (r⊥,k ) = max , s=1 zs,as ξs (as ) −1 1≤t≤T +1
4εL , ∆k
νk = Lx (ζk + Sk γk ) = Lx ζk + 4S∆kkεL
,
and the cumulative candidate residual width T X CRWT (r⊥,k ) = max ξt (a) − min ξt (a) .
S k = Sk + ζk . r βt0 = R
t=1
k log 1 +
2
(t−1)Lx λk
+ 2 log 1δ +
√ λ Sk,
r AT =
T L2 2T k log 1 + λkx .
Then, with probability at least 1 − δ, simultaneously for all T ≥ 1, Reg(T ) ≤ 2βT0 +1 AT + 2νk A2T + 2νk T T L2 = 2βT0 +1 AT + 4νk T k log 1 + λkx + 2νk T. √ e Suppressing logarithmic factors, Reg(T ) = O k T + Lx (ζk + Sk εL /∆k )kT . If ζk = 0 and εL = 0, then νk = 0 √ e and the bound reduces to O(k T ). If νk is unknown it must be replaced by an upper bound or selected by a doubling or grid wrapper; otherwise the result is an oracle bound. The εL /∆k dependence is the key takeaway: a large spectral gap protects against graph noise, while a small gap amplifies it.
Vt
a∈At
a∈At
SRLT is the self-normalized bias that the high-frequency residual injects into the regression updates; CRWT is the amount by which the residual can change the ordering of arms within each candidate set. In the node-arm case (xt,a = ea , r⊥,k = U>k c>k ), both are determined by where the high-frequency graph signal lives and which arms the bandit actually compares: a strictly finer characterization than the scalar tail ζk . Theorem 5 (A posteriori oracle residual bound). Assume the noise and bounded projected-feature conditions in Assumption 2. Fix a horizon T and suppose GraphDR-LinUCB is bk , λ ≥ L2x , and confidence radius βt = βt0 + BT run with E with BT ≥ SRLT (r⊥,k ), where r √ (t−1)L2 0 bk⊤ θ⋆ , βt = R k log 1 + λk x + 2 log 1δ + λ E 2
r AT =
2
TL
2T k log 1 + λkx .
Then, with probability at least 1 − δ, Reg(T ) ≤ 2βT0 +1 AT + 2BT AT + CRWT (r⊥,k ). In particular, the oracle choice BT = SRLT (r⊥,k ) yields Reg(T ) ≤ 2βT0 +1 AT + 2SRLT (r⊥,k )AT + CRWT (r⊥,k ).
Proposition 6 (What happens without residual-radius inflation). If the same algorithm is run with the smaller radius βt0 only, the same proof gives the valid bound
2142
Cumulative regret R(T = 20,000)
This is an a posteriori oracle inequality: BT depends on the unknown θ⋆ and the realized trajectory. Proposition 6 below characterizes exactly what is lost when the confidence radius is not inflated, explaining why an estimate of SRLT is needed for an implementable algorithm.
103
1226
778 481
102 31
B UC
+Lin
PCA
Reg(T ) ≤ 2βT0 +1 AT + SRLT (r⊥,k )AT
dom
Ran
led huff ol) R-s ontr phD (c Gra
CB
LinU
JL+
CBLinU
full
CB inU rs) R+L (ou
phD Gra
Method
+ T SRLT (r⊥,k ) + CRWT (r⊥,k ). Thus the clean 2SRLT AT oracle term requires either a known upper bound on SRLT or an estimated-residual confidence inflation. Without inflation, the comparator arm is not the played arm, and its uncertainty cannot be collapsed by the elliptical-potential lemma. The oracle bound becomes implementable by replacing the unknown residual with a pilot estimate. Theorem 7 (Estimated-residual horizon oracle bound). Let rb be a pilot estimate of r⊥,k obtained from data independent of the bandit noise used in the regret run, with ∥b r − r⊥,k ∥2 ≤ er and ∥xt,a ∥2 ≤ b b and a computable leverage Lx . Define ξt (a) = x⊤ t,a r P b bound BT ≥ max1≤t≤T +1 zs,a ξbs (as ) . Run s<t
958
s
Vt−1 0 b GraphDR-LinUCB with radius βt = βt + BT + Lx er AT .
Then, on the same high-probability event as Theorem 5, bT + Lx er AT )AT Reg(T ) ≤ 2βT0 +1 AT + 2(B [ T (b + CRW r) + 2Lx er T, PT ⊤ [ T (b b). To where CRW r) = b − mina x⊤ t,a r t=1 (maxa xt,a r be genuinely online, use the predictable radii βt = βt0 + b bt + Lx er At with B bt = maxu≤t P B ; s<u zs ξs (as ) −1 the stated horizon-T form is the special case at t = T .
Vu
Figure 2: Main synthetic comparison with the graphshuffle control. GraphDR+LinUCB dominates; the shuffled eigenspace collapses toward the random-policy level.
Synthetic Experiments We validate the dimension-reduction mechanism on controlled synthetic graphs where the reward subspace is known by construction. Arms are graph nodes with one-hot features (d = n), and θ⋆ = Uk α⋆ / ∥Uk α⋆ ∥ uses the true bottom-k nontrivial Laplacian eigenvectors, so the reward is graph-smooth by design. All methods compared are: Random; LinUCB-full (d = n); principal component analysis (PCA)+LinUCB; Johnson-Lindenstrauss (JL)+LinUCB; GraphDR+LinUCB; and GraphDR-shuffled, the graphshuffle control that projects with the bottom-k nontrivial eigenvectors of a node-permuted copy of the same graph. The shuffle control has the same projected dimension as GraphDR but a graph-misaligned eigenspace; any genuine gain must collapse when it is applied, and in every experiment below, it does. Regret R(T ) is the mean ± standard error over 8 seeds; LinUCB uses Sherman-Morrison updates. Main comparison. On a stochastic block model (SBM) with n = d = 200, C = k ⋆ = 5 communities, and T = 20,000, GraphDR-LinUCB reduces regret by more than 15× relative to full LinUCB and 69× relative to PCA (Figure 2):
Two corollaries bound the range of behaviour. First, the generic theorem is only a loose special case of Theorem 5.
Method
R(T ) ↓
± s.e.m.
Corollary 8 (Generic theorem as a loose special case). If |ξt (a)| ≤ νk for all t, a, then SRLT (r⊥,k ) ≤ νk AT and CRWT (r⊥,k ) ≤ 2νk T . Substituting these into the oracle version of Theorem 5 with BT = νk AT recovers Theorem 4, b ⊤ θ⋆ by S k . up to the harmless replacement of E k
PCA+LinUCB Random GraphDR-shuffled (control) JL+LinUCB LinUCB-full (d = 200) GraphDR+LinUCB
2152.3 1226.0 957.8 777.8 480.8 31.3
9.9 2.8 6.9 4.5 2.7 0.7
2
Corollary 9 (Benign residuals yield sublinear extra √ bias). On any problem sequence√with SRLT (r⊥,k ) = O( k log T ) and CRWT (r⊥,k ) = O( T ), the oracle-inflated algorithm √ √ e e of √ Theorem 5 gives O(k T) + √ Reg(T ) = O(k T ) + √ e e O( T ) = O(k T ), since SRLT AT = O(k T ), so the high-frequency residual contributes only sublinear regret. These conditions hold, for example, when the residual is nearly common-mode inside most candidate sets and its product with the played low-frequency features exhibits selfnormalized cancellation rather than worst-case alignment.
The shuffle control collapses toward the random-policy level (957.8), showing the gain is structural rather than merely dimensional. PCA performs poorly because one-hot features are isotropic and carry no variance signal. Dimension scaling. Fixing k ⋆ = 5 and scaling d = n from 60 to 800, GraphDR regret stays nearly flat (from 22.2 to 40.6, a 1.8× growth) while full-dimensional LinUCB grows steeply (from 183.0 to 852.1, a 4.7× growth), matching the predicted k-versus-d exploration cost of Corollary 2 (Figure 3).
4.7 × growth
LinUCB-full (481)
500
LinUCB-full GraphDR+LinUCB (ours)
LinUCB-full GraphDR+LinUCB (ours)
400
Cumulative regret R(T)
Cumulative regret R(T = 20,000)
103
1.8 × growth
102
300 200 100
k* =5 (29)
60
120
240
480
800
Ambient dimension d = n
Figure 3: Dimension scaling at fixed k ⋆ = 5. GraphDRLinUCB remains nearly flat as d = n grows; full LinUCB grows with ambient dimension. 2613
2546
2364
2297
Cumulative regret R(T)
103
418 102
18
led huff ol) R-s ontr phD (c
dom
Ran
Gra
JL+
LinU
CB
U
+Lin
PCA
CB
CB
LinU
-full
CB inU rs) R+L (ou
phD
Gra
Method
Figure 4: Second graph family: random geometric graph. GraphDR dominates; the graph-shuffle control collapses. Second graph family. On a random geometric graph (RGG, n = 200, radius 0.16) the same pattern holds: GraphDR attains R(T ) = 18.1 against 417.8 for full LinUCB and over 2000 for PCA, JL, and Random, with the shuffle control collapsing to 2544.6 (Figure 4). k-sweep. Sweeping the projected dimension at fixed k ⋆ = 5 on the SBM confirms that regret is minimized exactly at k = 5 and rises on both sides: too few dimensions omit signal; too many reintroduce exploration cost. The regret at k = 1, 2, 3, 5, 8, 12, 20 is 419.9, 384.2, 98.6, 28.7, 39.5, 55.4, 69.5 (Figure 5). Noise stress test and robust theorem validation. When G is observed under edge-flip noise, k must be selected from a noisy spectrum. The bootstrap and naive eigengap estimators return identical b k at every noise level; under heavier b noise k degrades (4 → 2 → 1) with measurable regret cost. A complementary stress test directly probes the misspecification envelope νk by measuring ζk and εL in each run: regret rises monotonically with both terms (pooled Spearman 0.68 across 16 runs).
Real-Data Benchmarks We evaluate on six real graph-bandit datasets: four recommendation graphs (MovieLens-100k/1M [25], Amazon Digital Music, LastFM/HetRec) and two non-recommendation
1 2 3
5
8
12
Projected dimension k
20
Figure 5: Regret versus projected dimension k. The minimum is at the true spectral dimension k ⋆ = 5.
graphs (MIND-small news [11], ogbn-arxiv citation [16]). Items, artists, papers, or news articles are arms; features are node indicators; the graph is built from co-rating, colistening, citation, or category and co-click relations; and rewards are calibrated from real ratings, plays, labels, or click-through statistics. All runs report cumulative regret at T = 20,000 over 5 seeds. Full dataset construction, perdataset MovieLens results, and the measured spectral quantities (b k, eigengap, and ζk ) are in the appendix. Cross-dataset summary. Table 2 shows GraphDRLinUCB beats full LinUCB on five of six datasets; the exception is ogbn-arxiv, where the citation-graph eigenspace is misaligned with the subject-label reward (ζk = 0.96). The GraphDR-versus-PCA comparison is more nuanced: GraphDR leads on four datasets (MovieLens-100k, Amazon, LastFM, MIND), while PCA wins on MovieLens-1M and ogbn-arxiv. At scale and when the reward is only weakly smooth, learned content variance can carry signal that PCA exploits better than the graph. The scalar reward tail ζk partially but not fully predicts this: ogbn-arxiv (0.96) is GraphDR’s clearest failure, yet MIND has the largest tail (0.99) and GraphDR wins decisively. The structure-specific theorem explains the discrepancy; what matters is not total high-frequency energy but whether the residual creates large candidate-set width or residual leverage along the played path. Comparison against graph-aware baselines. The decisive test for a graph-DR contribution is whether the algorithm beats bandits that already exploit the graph. Table 3 compares against SpectralUCB [34]: LinUCB in the full Laplacian eigenbasis with a per-eigenvalue smoothness penalty and no hard truncation, and Laplacian-regularized LinUCB [38]: full-d LinUCB with graph-smoothness regularization replacing ridge. GraphDR-LinUCB’s advantage holds against graphaware competitors on every graph-smooth dataset; on the misaligned ogbn-arxiv (ζk = 0.96), Laplacian-regularized LinUCB is the safer choice. To isolate the projection map from the feature source, a matched experiment replaces content-PCA with graph-only PCA (top-k singular vectors of A, the same graph-only input
Dataset
ζk
GraphDR
PCA
full LinUCB
shuffle
MovieLens-100k MovieLens-1M Amazon (Dig. Music) LastFM (HetRec) ogbn-arxiv MIND-small
0.67 0.68 0.86 0.90 0.96 0.99
238.4 273.3 309.9 412.1 667.6 415.0
331.5 186.7 338.6 508.5 258.5 887.7
615.0 592.6 463.4 678.9 492.2 780.5
712.7 650.2 526.4 774.3 602.1 943.9
Table 2: Cumulative regret R(T = 20,000) across six real graph-bandit datasets (top-1500 nodes each, 5 seeds; lowest in bold). GraphDR-LinUCB beats full LinUCB on five of six datasets, failing only on ogbn-arxiv where the citation-graph eigenspace is misaligned with the subject-label reward. The graph-shuffle control is always near-random. GraphDR wins on 4/6 against PCA; the scalar tail ζk partially but not fully predicts the pattern. Dataset
GraphDR
SpectralUCB
Laplacian-reg
PCA
full LinUCB
Synthetic SBM MovieLens-100k MovieLens-1M Amazon LastFM MIND-small ogbn-arxiv
31.3 122.7 147.7 148.6 186.4 169.4 277.0
466.2 256.0 245.1 195.0 282.7 341.7 210.8
462.1 247.2 238.0 189.4 276.9 325.9 203.2
2157.6 184.7 199.4 227.2 286.3 358.1 228.2
484.9 259.1 250.6 196.0 285.9 346.1 214.8
Table 3: Cumulative regret R(T ) against graph-aware bandits ( T =20000, 5 seeds synthetic; lowest per row in bold). GraphDRLinUCB beats both SpectralUCB and Laplacian-regularized LinUCB on the synthetic benchmark and on five of six real datasets. The single exception is ogbn-arxiv (ζk =0.96): even soft graph-aware methods beat hard bottom-k projection when the eigenspace is misaligned with the reward. The advantage of hard spectral truncation over soft eigenvalue-penalized smoothing is that truncation entirely removes the exploration cost of high-frequency directions rather than merely down-weighting it.
GraphDR receives): both graph-spectral maps beat graphblind baselines on most datasets, and GraphDR and graphPCA split 3–3 given identical input, confirming the advantage is structural. Diagnostic. A theory-motivated diagnostic Gk based on the residual quantities of Theorem 5 was evaluated but failed to outperform ζk on the signed gap; we replace it with the computable Γk below.
A working selection rule: the subspace-capture margin The structure-specific theorem says a reducer hurts the learner only through the reward energy it fails to keep. The GraphDR-vs-PCA contest is therefore most directly predicted not by the absolute graph tail ζk , but by a comparison of how much reward energy each reducer’s subspace captures. Let Uk be GraphDR’s bottom-k nontrivial Laplacian eigenbasis and P the competing reducer’s k-dimensional basis (contentPCA here). Define the subspace-capture margin Γk = =
2
2
Uk⊤ θ 2 −
P ⊤θ 2 2
Uk⊤ θ | {z }2
graph low-freq energy kept
−
2
P ⊤θ | {z }2
,
competitor energy kept
the (squared, unit-norm-reward) reward energy GraphDR’s subspace captures minus that the competitor captures. Γk > 0 predicts GraphDR; Γk < 0 predicts the competitor. Unlike ζk , which only sees GraphDR’s own tail, Γk is a head-to-
head alignment statistic and is computable from the same pilot reward estimate θb the diagnostic Gk already requires. Validated on all six real datasets, the fitted-threshold rule is leave-one-out correct on 6/6; the zero-parameter sign rule Γk > 0 is correct on 5/6, with the lone miss at the near-tie Γk = −0.008 (MIND-small). Against the dead diagnostic Gk (|ρs | ≈ 0.11, 2/6 leaveone-out) and the scalar tail ζk (2/6), Γk is the clear headline rule; the eigengap ∆k correlates at 0.83 but reaches only 4/6 leave-one-out and lacks mechanistic justification for the head-to-head comparison.
Conclusion We presented GraphDR-LinUCB, a reduction from graphsmooth contextual bandits to k-dimensional linear bandits via Laplacian eigenspace projection. The central theoretical insight is that the high-frequency reward component need not cost a linear-in-T penalty: its actual cost is governed by two realized graph quantities, residual leverage and candidateset residual width, rather than by the tail energy ζk alone. This structure-specific view replaces worst-case misspecification theory with a finer, graph-aware accounting, and the subspace-capture margin Γk translates this accounting into a practical, threshold-free selection rule. Graph-shuffle controls on every configuration confirm the gain is structural, and synthetic and real-data experiments validate the approach across recommendation, news, and citation graphs.
References [1] Abbasi-Yadkori, Y.; Pál, D.; and Szepesvári, C. 2011. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems. [2] Agarwal, A.; Luo, H.; Neyshabur, B.; and Schapire, R. E. 2017. Corralling a band of bandit algorithms. In Conference on Learning Theory. [3] Auer, P. 2002. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3: 397–422. [4] Belkin, M.; and Niyogi, P. 2003. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 15(6): 1373–1396. [5] Cesa-Bianchi, N.; Gentile, C.; and Zappella, G. 2013. A gang of bandits. In Advances in Neural Information Processing Systems. [6] Chapelle, O.; and Li, L. 2011. An empirical evaluation of Thompson sampling. In Advances in Neural Information Processing Systems. [7] Chu, W.; Li, L.; Reyzin, L.; and Schapire, R. E. 2011. Contextual Bandits with Linear Payoff Functions. In International Conference on Artificial Intelligence and Statistics. [8] Dai, Y.; Golrezaei, N.; and Jaillet, P. 2026. Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts. arXiv:2606.14929. [9] Dani, V.; Hayes, T. P.; and Kakade, S. M. 2008. Stochastic Linear Optimization under Bandit Feedback. In Conference on Learning Theory. [10] Davis, C.; and Kahan, W. M. 1970. The rotation of eigenvectors by a perturbation. III. SIAM Journal on Numerical Analysis, 7(1): 1–46. [11] Dudík, M.; Langford, J.; and Li, L. 2011. Doubly robust policy evaluation and learning. In International Conference on Machine Learning. [12] Foster, D. J.; Gentile, C.; Mohri, M.; and Zimmert, J. 2020. Adapting to misspecification in contextual bandits. In Advances in Neural Information Processing Systems. [13] Gentile, C.; Li, S.; and Zappella, G. 2014. Online clustering of bandits. In International Conference on Machine Learning. [14] Ghojogh, B.; Ghodsi, A.; Karray, F.; and Crowley, M. 2021. Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Survey. arXiv:2106.02154. [15] Hamilton, W. L.; Ying, R.; and Leskovec, J. 2017. Inductive Representation Learning on Large Graphs. arXiv:1706.02216. [16] Hu, W.; Fey, M.; Zitnik, M.; Dong, Y.; Ren, H.; Liu, B.; Catasta, M.; and Leskovec, J. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv:2005.00687.
[17] Huang, R.; and Huang, Z. 2025. Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback. arXiv preprint arXiv:2502.04678. [18] Jamshidi, F.; Shahverdikondori, M.; and Kiyavash, N. 2025. Graph-Dependent Regret Bounds in MultiArmed Bandits with Interference. arXiv:2503.07555. [19] Jedra, Y.; Réveillard, W.; Stojanovic, S.; and Proutiere, A. 2024. Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery. arXiv:2402.15739. [20] Jun, K.-S.; Willett, R.; Wright, S.; and Nowak, R. 2019. Bilinear Bandits with Low-rank Structure. arXiv:1901.02470. [21] Khosravi, H.; and Huo, X. 2026. Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity. arXiv:2605.20269. [22] Kipf, T. N.; and Welling, M. 2017. Semi-Supervised Classification with Graph Convolutional Networks. arXiv:1609.02907. [23] Lattimore, T.; and Szepesvári, C. 2020. Bandit Algorithms. Cambridge University Press. [24] Lattimore, T.; Szepesvári, C.; and Weisz, G. 2019. Learning with good feature representations in bandits and in RL with a generative model. In International Conference on Machine Learning. [25] Li, L.; Chu, W.; Langford, J.; and Schapire, R. E. 2010. A contextual-bandit approach to personalized news article recommendation. In International Conference on World Wide Web. [26] Mannor, S.; and Shamir, O. 2011. From Bandits to Experts: On the Value of Side-Observations. arXiv:1106.2436. [27] Ng, A. Y.; Jordan, M. I.; and Weiss, Y. 2001. On Spectral Clustering: Analysis and an Algorithm. In Advances in Neural Information Processing Systems. [28] Pacchiano, A.; Phan, M.; Abbasi-Yadkori, Y.; Rao, A.; Zimmert, J.; Lattimore, T.; and Szepesvari, C. 2020. Model Selection in Contextual Stochastic Bandit Problems. arXiv:2003.01704. [29] Paschalidis, P.; Zhang, R.; and Li, N. 2024. Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis. In American Control Conference (ACC). [30] Qi, H.; Guo, F.-Y.; Zhu, L.; Zhang, Q.; and Li, X. 2025. Graph Feedback Bandits on Similar Arms: With and Without Graph Structures. arXiv preprint arXiv:2501.14314. [31] Qiu, H.; Zhang, M.; and Cesa-Bianchi, N. 2026. Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach. arXiv preprint arXiv:2602.06404. [32] Russo, D.; Van Roy, B.; Kazerouni, A.; Osband, I.; and Wen, Z. 2017. A Tutorial on Thompson Sampling. arXiv:1707.02038. [33] Shuman, D. I.; Narang, S. K.; Frossard, P.; Ortega, A.; and Vandergheynst, P. 2013. The emerging field of signal processing on graphs. IEEE Signal Processing Magazine, 30(3): 83–98.
[34] Valko, M.; Munos, R.; Kveton, B.; and Kocák, T. 2014. Spectral bandits for smooth graph functions. In International Conference on Machine Learning. [35] von Luxburg, U. 2007. A Tutorial on Spectral Clustering. arXiv:0711.0189. [36] Wang, Y.; Li, J.; Kang, Y.; Gao, S.; and Xiao, Z. 2025. Generalized Low-Rank Matrix Contextual Bandits with Graph Information. arXiv:2507.17528. [37] Wen, D.; Yin, H.; Zhang, X.; Zhao, P.; Zhang, L.; and Wei, Z. 2024. Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching. arXiv preprint arXiv:2410.10258. [38] Yang, K.; Toni, L.; and Dong, X. 2020. Laplacianregularized graph bandits: Algorithms and theoretical analysis. In International Conference on Artificial Intelligence and Statistics. [39] Yu, X. 2019. Contextual Bandits with Random Projection. arXiv:1903.08600. [40] Zhao, H.; Ye, C.; Gu, Q.; and Zhang, T. 2024. Sharp Analysis for KL-Regularized Contextual Bandits and RLHF. arXiv:2411.04625.
Proofs This appendix contains the proofs of all results stated in the Theory section, in the order they appear. Each proof begins with a brief sketch of the key step to orient before the formal argument. Proof of Theorem 1. Sketch. The projection Ek⊤ makes the problem exactly k-dimensional; the standard self-normalized concentration and elliptical potential arguments then apply directly in Rk . Let zt = zt,at . Under Assumption 1, yt = zt⊤ α⋆ + ηt . The ridge estimate satisfies α bt − α⋆ = Vt−1
t−1 X
Proof of Lemma 3. Sketch. Weyl’s inequality controls the eigenvalue shift; Davis–Kahan then bounds the projector rotation by the shift divided by the gap. b differs from the By Weyl’s inequality, each eigenvalue of L corresponding eigenvalue of L by at most εL , so the separation between the perturbed bottom-k cluster and the rest is at least ∆k − 2εL ≥ ∆k /2. The Davis–Kahan sin Θ theorem b b k − Πk ≤ 2∥L−L∥2 ≤ for symmetric matrices gives Π ∆k −2εL
2
b k )Πk 4εL /∆k . The second inequality holds because (I − Π is a cross-projector bounded in operator norm by the distance between projectors. Proof of Theorem 4. Sketch. Decompose θ⋆ into its insubspace part and high-frequency residual; bound the residual’s effect on the regression updates by νk pointwise; then apply the standard optimism argument with an inflated confidence radius. b k θ⋆ +(I − Π b k )θ⋆ and set α b ⊤ θ⋆ , Decompose θ⋆ = Π b⋆ = E k ⋆ ⋆ ⋆ ⋆ b b so Πk θ = Ek α b and ∥b α ∥2 ≤ ∥θ ∥2 ≤ Sk + ζk = S k . Moreover, b k )θ⋆ (I − Π
2
b k )(Πk θ⋆ + rk ) = (I − Π b k )Πk ≤ (I − Π
2
2
b k )rk ∥Πk θ⋆ ∥2 + (I − Π
≤ γk Sk + ζk . b ⋆ For any arm define ξt,a = x⊤ t,a (I − Πk )θ ; then |ξt,a | ≤ ⋆ b k )θ⋆ ≤ Lx (ζk + Sk γk ) = νk , and x⊤ Lx (I − Π t,a θ = 2
⊤ ⋆ zt,a α b + ξt,a with |ξt,a | ≤ νk . For the selected arm write b⋆ + ηt + ξt and zt = zt,at , ξt = ξt,at , so yt = zt⊤ α X X α bt − α b⋆ = Vt−1 zs ηs + Vt−1 zs ξs − λVt−1 α b⋆ . s<t
s<t
P On the self-normalized event, s<t zs ηs Vt−1 q 2 (t−1)L R k log(1 + λk x ) + 2 log 1δ and λ ∥b α⋆ ∥V −1 t √ λ S k . Since |ξs | ≤ νk and Vt ⪰ Vs , X P ∥zs ∥Vs−1 s<t zs ξs V −1 ≤ νk
zs ηs − λVt−1 α⋆ .
s=1
Taking the Vt -norm and using Vt ⪰ λIk , √ Pt−1 ∥b αt − α⋆ ∥Vt ≤ + λS. s=1 zs ηs −1 Vt
t
The self-normalized martingale inequality gives, with probability at least 1 − δ, uniformly over t, r Pt−1 det(Vt )1/2 z η ≤ R 2 log . s=1 s s −1 det(λIk )1/2 δ
≤ ≤
s<t
r ≤ νk
(t−1)L2 2(t − 1)k log 1 + λk x .
(t−1)L2 det(Vt ) Since ∥zs ∥2 ≤ Lx , log det(λI ≤ k log(1 + λk x ), so k) ∥b αt − α⋆ ∥Vt ≤ βt for all t on this event. For any arm, ⊤ Cauchy–Schwarz gives |zt,a (b αt − α⋆ )| ≤ βt ∥zt,a ∥V −1 , so t the UCB is optimistic. Letting a⋆t be optimal, the standard ⋆ optimism argument yields x⊤ θ⋆ −x⊤ t,at θ ≤ 2βt ∥zt ∥V −1 . t,a⋆ t
Hence ∥b αt − α b⋆ ∥Vt ≤ βt0 + q (t−1)L2x ⊤ ⋆ νk 2(t − 1)k log(1 + λk ). With µt (a) = xt,a θ , ⊤ ⋆ qt (a) = zt,a α b , we have |µt − qt | ≤ νk , and for a⋆t ∈ arg max µt , µt (a⋆t ) − µt (at ) ≤ qt (a⋆t ) − qt (at ) + 2νk . The optimism argument applied to qt with the inflated radius and summation give Reg(T ) ≤ 2βT0 +1 AT +2νk A2T +2νk T .
Summing and using monotonicity of βt , Reg(T ) ≤ PT 2 2βT +1 t=1 ∥zt ∥V −1 . Because λ ≥ L2x , ∥zt ∥V −1 ≤ 1, t t PT and the elliptical potential lemma gives t=1 ∥zt ∥V −1 ≤ t q T L2x 2T k log(1 + λk ). Substitution proves the theorem.
Why the generic bound is too pessimistic. Theorem 4 uses only the uniform envelope |ξt,a | ≤ νk , treating the residual as an adversary that can corrupt every regression update and change the best arm every round. In graph problems ξt,a is not arbitrary: it is the value of the high-frequency
Vt
t
2
b k )θ⋆ on the arms that actually appear. graph signal (I − Π The next theorem keeps this structure instead of collapsing it into the scalar νk .
P ≤ Proof of Corollary 8. s<t zs ξs (as ) Vt−1 P νk s<t ∥zs ∥Vs−1 ≤ νk AT , and every candidate-set residual range is at most 2νk .
Proof of Theorem 5. Sketch. Decompose the instantaneous regret into a low-frequency part (controlled by the UCB optimism in the projected space) and a high-frequency part (controlled by CRWT summed over rounds); the regression bias from the residual is absorbed into SRLT . ⋆ ⊤ b⊤ ⋆ Write µt (a) = x⊤ t,a θ , qt (a) = zt,a Ek θ , so µt (a) = qt (a) + ξt (a) and yt = qt (at ) + ηt + ξt (at ). The ridge error decomposes as X X bk⊤ θ⋆ = Vt−1 bk⊤ θ⋆ . α bt −E zs ηs +Vt−1 zs ξs (as )−λVt−1 E
What is graph-specific about the theorem. In the one-hot node-arm case xt,a = ea and r⊥,k = U>k c>k is the highfrequency graph signal, so ξt (a) = e⊤ a U>k c>k . Thus CRWT is the cumulative range of the high-frequency graph signal over the candidate sets, while SRLT is the self-normalized cross-correlation between low-frequency coordinates Uk (a) and high-frequency residual values (U>k c>k )a along the played path. This is sharper than ζk because it knows where the residual lives on the graph and which arms the bandit compares.
s<t
s<t
b ⊤ θ⋆ bt − E On the self-normalized event, for all t, α k
Projection Identity
≤ Vt
βt0 + SRLT (r⊥,k ) ≤ βt0 + BT . Because the algorithm uses radius βt0 + BT , its UCB is optimistic for the projected means qt . Letting aqt ∈ arg maxa qt (a), the LinUCB argument gives qt (aqt ) − qt (at ) ≤ 2(βt0 + BT ) ∥zt ∥V −1 . Since t a⋆t maximizes µt rather than qt ,
2
If θ = Ek α and Ek⊤ Ek = Ik , then ∥θ⋆ ∥2 = 2 (α⋆ )⊤ Ek⊤ Ek α⋆ = ∥α⋆ ∥2 , and for every x ∈ Rd , x⊤ θ⋆ = ⊤ ⊤ ⋆ (Ek x) α . Thus projection to Ek⊤ x is signal-lossless under exact graph smoothness. ⋆
⋆
Elliptical Potential Bound
µt (a⋆t ) − µt (at ) = qt (a⋆t ) − qt (at ) + ξt (a⋆t ) − ξt (at ) ⊤ 2 Let V1 = λIk , Vt+1 = Vt + zt zt , λ ≥ Lx , ∥zt ∥2 ≤ q 2 ≤ qt (at ) − qt (at ) + max ξt (a) − min ξt (a) . Lx . Then ∥zt ∥V −1 ≤ 1, and by the matrix determia
a
t
Summing and using the elliptical potential bound proves the theorem.
2
nant lemma det(Vt+1 ) = det(Vt )(1 + ∥zt ∥V −1 ). Since t PT 2 u ≤ 2 log(1 + u) for u ∈ [0, 1], ∥z t ∥V −1 ≤ t=1 t
Proof of Proposition 6. The confidence event still gives ⊤ |qt (a) − zt,a α bt | ≤ (βt0 + SRLT ) ∥zt,a ∥V −1 , but the alt gorithm only maximizes the UCB with radius βt0 , so ⊤ ⊤ zt,a bt + βt0 zt,aqt V −1 ≤ zt,a α b + βt0 ∥zt,at ∥V −1 . Comqα t t t t t bining, qt (aqt )−qt (at ) ≤ SRLT zt,aqt V −1 +(2βt0 +SRLT ) ∥zt ∥V −1 . t
t
The played-arm terms sum to at most (2βT0 +1 + SRLT )AT , while zt,aqt V −1 ≤ 1 under λ ≥ L2x , giving the extra t T SRLT term. Adding CRWT proves the claim. Proof of Theorem 7. The residual-leverage estimaP b tion error obeys z (ξ (a ) − ξ (a )) ≤ s s s<t s s s Vt−1 P Lx er s<t ∥zs ∥Vs−1 ≤ Lx er AT , since |x⊤ b)| ≤ s,as (r⊥,k − r b Lx er . Hence BT + Lx er AT upper-bounds SRLT (r⊥,k ). The true candidate residual width differs from the estimated one by at most 2Lx er T . Applying Theorem 5 with bT + Lx er AT proves the result. BT = B The implementable advantage is contingent on pilot quality. Theorem 7 improves on Theorem 4 only when the pie r kT ) and lot estimate is good. The terms 2Lx er A2T = O(e 2Lx er T are linear in T , so a poor pilot (er = Θ(1)) recovers the generic linear bias. The estimated-residual bound is most useful when a cheap exploration prefix or logged data yields bT , CRW [ T are small, precisely er = o(1) and the realized B the benign-residual regime the diagnostic in Appendix is designed to detect.
T +1 ) 2 log det(V det(V1 ) , and the trace–determinant inequality gives PT T L2x T +1 ) log det(V t=1 ∥zt ∥Vt−1 ≤ det(V1 ) ≤ k log(1 + λk ). Hence q 2 TL 2T k log(1 + λkx ).
A Predictive Diagnostic and Its Held-Out Evaluation Diagnostic construction. The real-data picture in the Real-Data Benchmarks section exposes a gap that the scalar tail ζk cannot close: ζk is large on both MIND (0.99) and ogbn-arxiv (0.96), yet GraphDR wins decisively on MIND and loses on ogbn-arxiv. The structure-specific theorem says the deciding factor is not total high-frequency energy but whether the residual is harmless in the candidate distribution. This motivates a computable alignment diagnostic. Given a pilot reward estimate θb from logged data, validation data, or a short exploration prefix, define rb⊥,k = b For a candidate-set sample D = {At }M we b k )θ. (I − Π t=1 measure the empirical analogues of the two theorem quantities: the candidate residual width M X [ k (D) = 1 max x⊤ b⊥,k − min x⊤ b⊥,k , CRW t,a r t,a r a∈At M t=1 a∈At d k (D) = and an approximate residual leverage SRL P ⊤ max1≤t≤M +1 bs,as xs,as rb⊥,k Vb −1 computed along s<t z t a short greedy or random prefix, combined into r 2 d k (D). [ k (D)+2 2k log(1 + M Lx /(λk)) SRL Gk (D) = CRW M
Small Gk is hypothesized to indicate that GraphDR should be competitive; large Gk suggests PCA, full LinUCB, or a Laplacian-regularized alternative may be safer.
lect GraphDR when Γk > 0; otherwise prefer PCA, full LinUCB, or a Laplacian-regularized baseline.
Held-out evaluation protocol. A binary outcome over six datasets cannot support fitting and validating a threshold rule, so we expand each base dataset into 150 problem instances by subsampling node-induced subgraphs at several sizes, varying k ∈ {2, 5, 10, 20, 40}, varying candidate-set construction (uniform, popularity-biased, neighbourhood-restricted), and edge-perturbing the graph at several noise levels. Each instance produces one tuple (ζk , SRLT , CRWT , Gk , RTGraphDR , RTPCA ). The primary test rank-correlates each predictor with the signed gap G−P := RTGraphDR − RTPCA (negative means GraphDR wins); the decision-rule test fits a threshold Yb (τ ) = 1{Gk ≤ τ } under leave-one-base-dataset-out.
Full Diagnostic-Validation Protocol
Results. The outcome is, on its declared primary test, negative, and we report it straight. Measured over the 150 instances, the absolute Spearman correlation with the signed gap is 0.252 for ζk , 0.07 for SRLT , 0.03 for CRWT , and 0.11 for Gk (the theorem-consistent normalization raises Gk ’s correlation from 0.036 to 0.106, still below ζk ). No structurespecific predictor beats ζk on rank correlation, so the declared positive criterion is not met. The leave-one-base-dataset-out decision-rule test is more favourable: Gk reaches held-out accuracy 0.62 versus 0.47 for ζk (and CRWT alone 0.63), so the realized residual quantities do help a held-out classifier. On the MIND-versus-ogbn separation that motivated the diagnostic, Gk does not separate the two cases (MIND 0.192 versus ogbn 0.137, the wrong direction), so the scalar collapse fails the specific case it was designed for. We therefore present Gk as a theory-motivated diagnostic with honest empirical characterization, not a validated model-selection rule. The structure-specific theorem stands on its own; the realized residual quantities carry some heldout classification signal; but a unit-weighted scalar collapse does not beat ζk , and a deployable rule would require a learned (SRLT , CRWT ) weighting and more base graphs.
Estimating the Residual Diagnostic The diagnostic Gk from the predictive diagnostic appendix is computed as follows. b from the training graph and compute E bk . 1. Build L 2. Fit a pilot reward model θb from a disjoint exploration prefix, logged data, or cross-fitting (a node reward estimate in the one-hot case; a ridge or doubly robust model with general features). b b k )θ. 3. Compute rb⊥,k = (I − Π [ k on held-out candidate sets by averaging 4. Estimate CRW the range of x⊤ b⊥,k over candidates. t,a r d k on a short simulated or logged prefix. 5. Estimate SRL 6. Compute the subspace-capture margin Γk = Uk⊤ θb P ⊤ θb
2 2
2
− 2
against the competing reducer’s basis P . Se-
The protocol behind the predictive diagnostic evaluation is specified here in full so that the negative primary result cannot be read as post hoc. The instance generation expands each of the five base datasets used in the diagnostic study (MovieLens100k, LastFM, Amazon, ogbn-arxiv, MIND-small; MovieLens-1M is omitted from the subgraph-resampled study) by subsampling node-induced subgraphs at sizes {400, 800, 1500}, varying k ∈ {2, 5, 10, 20, 40}, varying candidate-set construction across uniform, popularitybiased, and neighbourhood-restricted sampling, and edge-perturbing the graph at noise levels {0, 0.05}. This yields 150 instances, each producing one tuple (ζk , SRLT , CRWT , Gk , RTGraphDR , RTPCA ) at T =8000 over 3 seeds. The continuous target is the signed gap G − P := RTGraphDR − RTPCA (negative means GraphDR wins), and the binary target is Y = 1{RTGraphDR < RTPCA }. We report each of SRLT and CRWT separately, together with a two-dimensional logistic predictor on (SRLT , CRWT ), before collapsing to the scalar Gk . The primary test rankcorrelates (Spearman, Kendall) each predictor with G − P across instances. For the decision-rule claim we fit a threshold Yb (τ ) = 1{Gk ≤ τ } on training instances and evaluate held-out using leave-one-base-dataset-out, comparing against the analogous threshold rule on ζk by AUC and heldout accuracy. Because Gk depends on a pilot estimate rb, we also report Gk and its predictive power across pilot budgets. The measured correlations and held-out accuracies are reported in the predictive diagnostic appendix.
Real-Data Construction and Per-Dataset Results The six datasets comprise four recommendation graphs (MovieLens-100k/1M, Amazon Digital Music, LastFM/HetRec) and two non-recommendation graphs (MIND-small news, ogbn-arxiv citation). Table 4 records how each graph and bandit protocol is built. The two MovieLens datasets bracket the GraphDR-versusPCA boundary. On MovieLens-100k (n = 1682 items, an item–item kNN co-rating graph with 13,686 edges, real centered unit-normalized mean-rating reward), GraphDR attains the lowest regret, though by a small margin over PCA and far below the synthetic regime, consistent with the measured tail ζk = 0.67 (Table 6). The PCA baseline here uses learned item embeddings whereas GraphDR uses node indicators, so the comparison tests whether graph structure beats learned feature variance, not whether Laplacian projection beats PCA on the same input; the matched comparison is in the matchedcomparison appendix. On MovieLens-1M (top-1500 mostrated items, ζk = 0.68) GraphDR beats full LinUCB by 2.2× and the shuffle control collapses to near-random, but PCA wins: at scale learned item embeddings carry strong
Matched Comparison: Graph-Only PCA on the Same Input
Dataset
Graph construction
Bandit protocol
Result
MovieLens100k
Co-rating item kNN graph.
Table 6
MovieLens1M
Co-rating item kNN graph on top-1500 items. Co-rating product kNN graph.
Node-indicator arms, real meanrating reward; GraphDR vs. PCA/JL/full + shuffle. Identical protocol; tests scale. Node-indicator arms, real meanrating reward. Node-indicator arms, real CTR reward. Node-indicator arms, log play-count reward. Node-indicator arms, subject-label reward; nonrecommendation.
Table 2
The PCA baseline in the main body consumes learned item embeddings. To isolate the projection map from the feature source, we add graph-only PCA: PCA applied to the graph adjacency itself (the top-k right singular vectors of A), which consumes exactly the same graph-only information GraphDR receives, with no ratings or content. The only remaining difference from GraphDR is the projection criterion (top variance directions of A versus bottom-k low-frequency Laplacian eigenvectors).
Table 2
Subspace-Capture Margin: Full Validation
Amazon (Digital Music) MINDsmall LastFM HetRec
/
ogbn-arxiv
Article–article category/coclick graph. Artist co-listen kNN graph. Symmetrized paper citation graph.
Table 7
Table 2
Table 2
Table 4: Real-data benchmarks: four recommendation graphs and two non-recommendation graphs. All datasets use nodeindicator arm features (xi = ei , d = n) consistent with the graph-causal synthetic model.
Comparison to alternative selectors. Γk ’s Spearman rank-correlation with the signed gap is 0.49 and its leaveone-out accuracy is 6/6 (fitted) / 5/6 (zero-parameter), versus the original Gk ’s |ρs | ≈ 0.11 and ζk ’s 2/6. The eigengap ∆k alone rank-correlates at 0.83 but reaches only 4/6 leaveone-out and has no mechanistic justification for the head-tohead comparison against content-PCA; we report Γk as the headline rule and ∆k as a correlated secondary signal. With n = 6 base datasets we cannot certify a threshold law; the open task is to confirm this regularity on more base graphs and against the matched graph-PCA competitor.
Additional Synthetic Results This appendix collects the full synthetic results summarized in the Synthetic Experiments section.
variance signal that content-PCA exploits better than the graph when the reward is only weakly smooth (Table 7). Method
R(T ) ↓
± s.e.m.
GraphDR-shuffled (control) Random JL+LinUCB LinUCB-full (d = n) PCA+LinUCB GraphDR+LinUCB
712.7 704.2 653.4 615.0 331.5 238.4
3.2 1.9 3.3 1.2 3.6 2.1
Table 6: MovieLens-100k cumulative regret. GraphDR attains the lowest regret; the margin over PCA is small and far below the synthetic regime, consistent with ζk = 0.67.
Method
R(T ) ↓
± s.e.m.
Random JL+LinUCB GraphDR-shuffled (control) LinUCB-full (d = n) GraphDR+LinUCB PCA+LinUCB
677.6 660.0 650.2 592.6 273.3 186.7
1.7 1.9 2.9 1.9 5.7 2.5
Table 7: MovieLens-1M (top-1500 most-rated items), ζk = 0.68. GraphDR beats full LinUCB (2.2×) and the shuffle control collapses to near-random, but PCA wins.
Dimension scaling. 60 to 800:
Fixing k ⋆ = 5 and scaling d = n from
d=n
60
120
240
480
800
GraphDR R(T ) GraphDR slope Full LinUCB R(T ) Full LinUCB slope
22.2 0.16 183.0 1.33
18.6 0.14 354.8 2.58
31.5 0.23 607.0 4.35
26.8 0.20 848.8 5.91
40.6 0.29 852.1 5.82
GraphDR regret stays nearly flat as d grows while fulldimensional LinUCB grows substantially, matching the predicted k-versus-d exploration cost (Figure 3). Second graph family. On a random geometric graph (n = 200, radius 0.16): GraphDR R(T ) = 18.1 versus LinUCBfull 417.8, PCA 2045.5, JL 2364.1, Random 2613.0; the shuffle control collapses to 2544.6, near-random (Figure 4). Regret versus projected dimension k. Projecting onto the true bottom-k nontrivial eigenvectors in the SBM with k ⋆ = 5, regret at k = 1, 2, 3, 5, 8, 12, 20 is 419.9, 384.2, 98.6, 28.7, 39.5, 55.4, 69.5. Regret is minimized at k = k ⋆ = 5 and rises on both sides (Figure 5). Noisy graph stress test. When the graph is observed under edge-flip noise, the bootstrap estimator and naive eigengap estimator return identical b k at each noise level; under heavier noise b k degrades (4 → 2 → 1) with measurable regret cost, motivating Theorem 4.
Dataset
ζk
Uk⊤ θ
MovieLens-100k Amazon LastFM MIND-small MovieLens-1M ogbn-arxiv
0.67 0.86 0.90 0.99 0.68 0.96
0.528 0.265 0.183 0.023 0.532 0.101
2
2
P ⊤θ 0.389 0.128 0.154 0.031 0.771 0.341
Γk
GraphDR vs. PCA
+0.139 +0.137 +0.028 −0.008 −0.239 −0.240
win (−93.1) win (−28.7) win (−96.4) win (−472.7) lose (+86.6) lose (+409.1)
Table 9: The subspace-capture margin Γk predicts the GraphDR-vs-content-PCA outcome where ζk cannot. Rows sorted by Γk ; final column is the realized outcome (signed gap RGraphDR − RPCA in parentheses, negative = GraphDR wins). The fitted-threshold rule is leave-one-base-dataset-out correct on 6/6; the zero-parameter sign rule Γk > 0 is correct on 5/6 (lone miss: MIND at the near-tie Γk = −0.008, where both subspaces capture almost no reward energy yet GraphDR wins because content-PCA is itself far from the reward). Crucially, Γk orders ogbn-arxiv (−0.240, GraphDR’s documented failure) at the bottom while ζk cannot: MIND has the largest tail (0.99) yet GraphDR wins, exactly the inversion that defeated the scalar tail and the unit-weighted Gk . Validating the robust theorem. We measure ζk and εL in each run (n = 200 SBM, k ⋆ = 5, T = 20000, 5 seeds). Injecting reward energy outside the bottom-k subspace raises ζk from 0 to 0.71 and regret rises monotonically; holding the reward exactly smooth and perturbing edges raises εL from 0 to 0.48 and regret again rises monotonically (Table 10). Pooled Spearman(R, ρk ) = 0.68, monotone in binned medians.
Smoothness sweep (εL = 0): R(T ) vs. reward tail ζk ζk R(T )
0 28
0.11 47
0.24 121
0.39 271
0.55 505
0.71 801
0.43 445
0.48 590
Noise sweep (ζk = 0): R(T ) vs. εL εL R(T )
0 28
0.18 218
0.23 242
0.29 308
Table 10: Stress test consistent with the generic robust theorem: regret rises monotonically with each measured misspecification term. Pooled Spearman(R, ρk ) = 0.68.
Limitations and Additional Evaluation Several boundaries of the results deserve explicit statement. The structure-specific bound (Theorem 5) uses SRLT (r⊥,k ), which depends on the unknown θ⋆ ; we state it as an oracle inequality and make it implementable only through the estimated-residual variant of Theorem 7, whose advantage is contingent on a good pilot. If the residual has large candidate-set width every round, the residual term remains linear in T ; this cost is unavoidable without benignresidual structure. Our real-data protocol calibrates rewards from ratings and clicks rather than from a logged online experiment with known propensities. With logged propensities or an exploration log under a known logging policy p, one could report,
for a target policy π, N 1 X π(ai | xi ) ri , VbIPS (π) = N i=1 pi (ai | xi ) π(ai |xi ) i pi (ai |xi ) ri b VSNIPS (π) = P π(a |x ) . i i
P
i pi (ai |xi )
" N 1 X X b π(a | xi )b µ(xi , a) VDR (π) = N i=1 a # π(ai | xi ) + ri − µ b(xi , ai ) . pi (ai | xi ) A fully logged evaluation and an adaptive-k study (testing whether a corralling wrapper [2] matches oracle-k regret) are natural extensions left to future work. Replacing the nodeindicator arm features with learned graph embeddings [22, 15] and studying how embedding quality affects the spectral gap is a further direction, as is extending the Laplacianbased DR survey of [14] to the bandit feedback setting. We also prove only upper bounds; matching lower bounds for the εL /∆k dependence and for the residual leverage and candidate-width terms remain open.