When a new user arrives, a recommender knows almost nothing about them. The usual response is to find, as quickly as possible, one category the user clicks on and then keep serving it. That is efficient in the short term. It also builds a filter bubble (a self-reinforcing loop where the system only shows what it already thinks you like) within the user's first dozen interactions, before the system has had any chance to learn whether the user has other interests. Work on filter bubbles assumes users who already have long histories. Work on cold start optimizes for fast convergence. Neither asks what the first twenty recommendations should look like if the goal is to learn the user rather than to lock onto them.
We propose to model each user's taste as a smooth preference surface over the item embedding space, written as the sum of two parts: a population surface shared by everyone, and a user-specific deviation from it. Both are Gaussian processes, meaning probability distributions over functions that come with calibrated uncertainty. The two parts share one small set of anchor points in item space ("inducing points"), so the model scales to many users. Exploration for a new user is driven only by uncertainty in their deviation, so the system probes the regions where this particular user might differ from the crowd. Regions where the population is merely unsure, and regions the user's first click happens to sit in, do not drive exploration. The claim is that this targeting of exploration keeps early accuracy while measurably delaying or preventing early bubble formation.
Core Claim
The closest existing work is GPR4DUR (Density-based User Representation using Gaussian Process Regression for Multi-interest Personalized Retrieval). It represents each user as an exact Gaussian process regression over their own item interactions and uses UCB or Thompson sampling to reach niche interests, improving interest coverage and tail exposure. It motivates this proposal and also exposes the gap. Each user's GP is isolated and shares nothing with other users. For a new user the posterior is just the prior, so exploration at cold start is uninformed. Exact inference also costs cubic time in history length, which the authors concede limits it for long histories. We keep GPR4DUR's idea of a user as a surface over item space, but change three things: what is shared across users, which uncertainty drives exploration, and where the shared anchor points are placed.
Concretely, user $u$'s preference at item embedding $x$ is
$$ f_u(x) = g(x) + h_u(x), \qquad g \sim \mathcal{GP}(0, k_g), \quad h_u \sim \mathcal{GP}(0, k_h), $$
where $g$ is the population surface, $h_u$ is the user's deviation, and $k_g, k_h$ are kernels (similarity functions) over item embeddings. Both are approximated through the same $m$ inducing locations $Z$ in item space. The population posterior over $g$ and the kernel parameters are learned once from all warm users. Each user then stores only an $m$-dimensional Gaussian over their deviation's values at $Z$, updated in $O(m^2)$ per interaction, independent of history length. The exploration score is
$$ a_u(x) = \mu_u(x) + \beta\, \sigma_{h,u}(x), $$
where $\mu_u$ is the posterior mean of $f_u$, $\sigma_{h,u}$ is the posterior standard deviation of the deviation term alone, and $\beta$ trades off exploration against exploitation.
The design rests on a specific hypothesis about failure modes. A mean-greedy rule converges onto whatever the first positive click was near. A total-variance rule wastes its exploration on rare items the population knows little about, which are often simply bad. Deviation variance is high exactly where the user's own data has not yet tested whether they agree with the population, and this is the kind of exploration that keeps a cold-start session from collapsing.
Why Scalability Is Not Decorative
The cold-start case does not need scalable inference for its own sake: a GP over ten interactions is cheap. Scalability matters in two other places. First, learning a population kernel $k_g$ that encodes which regions of item space tend to be co-liked requires fitting one model to every training user's interactions, which can number in the millions. That is only feasible with sparse variational inference through shared inducing points. Second, a user's deviation posterior must keep updating as they warm up, without refitting on a growing history. This is where GPR4DUR's exact inference becomes the bottleneck.
Two scalable-GP results constrain the design. HIP-GP (Hierarchical Inducing Point Gaussian Process for Inter-domain Observations) reaches a million inducing points with FFT-based tricks, but only on regular grids in about four or fewer dimensions. That rules it out for 64-dimensional item embeddings, so we use unstructured inducing points with $m$ in the low thousands, below the roughly 10,000 where the file reports that standard stochastic variational GPs stall. Approximation-Aware Bayesian Optimization (Approximation-Aware Bayesian Optimization) shows that a limited inducing budget smooths away sharp local peaks. Placing inducing points by interaction density would put them all in popular regions and erase exactly the niche peaks that break bubbles. We therefore treat placement as a first-class design choice. Our default places inducing points to cover the item catalog (clustering over all item embeddings, not over interactions), and we test it directly against density-driven placement.
On the collaborative side, we take from the Tucker GP (Tucker Gaussian Process for Regression and Collaborative Filtering) the view that collaborative filtering is a GP over users and items. It scales by MAP estimation and so throws away the posterior variance that exploration needs. We keep a variational posterior instead. The population-plus-personal decomposition mirrors the objective in Collaborative Learning in Kernel-based Bandits for Distributed Users, which mixes local and global reward functions and compresses them with Nyström inducing points. That work is tested only on low-dimensional synthetic functions, and it does not separate the two sources of uncertainty for exploration, which is our central ingredient.
Research Program
Item embeddings come from a matrix factorization model trained on warm users only, so cold users never leak into the representation. We fit the population GP and the kernel hyperparameters for $k_g$ and $k_h$ by sparse variational inference on the warm users, with catalog-coverage inducing points.
For each simulated cold user we run an interactive session. Each round the system shows a slate of five items, observes feedback, and performs a rank-one update to the user's deviation posterior. The kernel stays fixed during the session. We accept this limitation knowingly: the file notes that fixed hyperparameters in streaming GPs (Recurrent Memory for Online Interdomain Gaussian Processes) prevent adapting to sharp preference shifts. Within a twenty-round cold session that matters less than over months.
The analysis has three parts. First, we decompose where each acquisition rule spends its exploration: in popular regions, in rare regions, or in regions holding the user's held-out interests. This tests the mechanism, not just the outcome. Second, we measure how the variance of $h_u$ shrinks as interactions accrue. This gives a natural point at which a user stops being "cold," with no hand-set threshold. Third, we run a cost study of update time and memory as history length grows from 10 to several thousand.
Proposed Experiments
We follow TaNP's cold-start protocol (Task-adaptive Neural Process for User Cold-Start Recommendation): users with at most ten support interactions on MovieLens-1M, Last.fm, and Gowalla. We add Amazon for tail exposure and Serendipity-2018, which carries human serendipity labels, for serendipity. Interactive sessions are evaluated by replay on held-out users who actually have long histories. Their logged positives define reward, and their full histories define their true set of interest clusters. Twenty rounds of five items are replayed from a cold start.
The metrics fall into four groups. Cumulative hit rate measures cold-start accuracy, and Precision@5 and NDCG on the TaNP split allow comparison with that protocol. Interest-wise Coverage, following GPR4DUR, counts how many of the user's held-out interest clusters are hit within the session. An early-bubble index is the share of rounds 11–20 spent in the single most-served cluster, relative to the entropy of the user's true cluster distribution. Finally, we report Serendipity@3, Div@5, and NDCG on Serendipity-2018, and negative log predictive density and interval coverage on held-out cold-user ratings as a check of calibration.
Baselines
The do-nothing reference is popularity followed by matrix-factorization greedy ranking once any interaction exists, with no exploration. It shows how fast a bubble forms by default.
The strongest serendipity method in the file is SOG (How does serendipity affect diversity in recommender systems? A serendipity-oriented greedy algorithm). It reranks SVD candidates by a weighted sum of relevance, diversity, profile dissimilarity, and unpopularity. On Serendipity-2018 it reports Serendipity@3 of 0.305, Div@5 of 0.371 (against SVD's 0.347), and NDCG of 0.899 (against SVD's 0.921). We run SOG on the same SVD candidate pools and tune its weights with the same search budget as our $\beta$. Beating it on this benchmark means matching or exceeding 0.305 Serendipity@3 at NDCG no lower than 0.899 in the cold subset, where its profile-dissimilarity term is known to be unreliable.
The strongest cold-start accuracy method is TaNP, which maps up to ten interactions to a predictive distribution through an amortized neural network. The file reports only relative gains, for example 4.2% Precision@5 on MovieLens-1M over MeLU and MAMO, and no absolute values were found on Lacuna. We therefore rerun TaNP on our splits with its published settings and an equal tuning budget. We use its predictive variance in the same UCB rule so that the comparison isolates the source of uncertainty. Beating it means comparable Precision@5 together with better calibration and a lower early-bubble index.
The closest structural baseline is GPR4DUR with exact per-user GPs and UCB. The file reports no absolute coverage or exposure value for it. We give it the same item embeddings and the same kernel family.
Three ablations isolate our ingredients. The first uses total-variance UCB instead of deviation-variance UCB. The second uses interaction-density inducing placement instead of catalog coverage. The third drops the shared population term, keeping only $h_u$, which recovers a sparse GPR4DUR.
Why not just…?
Why not just give GPR4DUR a population prior mean and keep exact inference? For cold users, exact inference is cheap, so this is a real threat. We include exactly this variant: an exact per-user GP whose prior mean is the matrix-factorization population score and whose kernel is fixed. If it matches our model on cumulative hits and the early-bubble index, then the learned shared covariance and the variance decomposition add nothing. The contribution would then shrink to constant-cost updates for warming users, and we would report it that way. Our expectation that it falls short rests on its uncertainty: a mean-only prior cannot tell population-uncertain regions from user-uncertain ones, so it behaves like the total-variance ablation.
Why not just use an epinet-style uncertainty head on a two-tower model with Thompson sampling? Epinet for Content Cold Start shows large live gains, including 17% more impressions for cold content. That result is for new items, and its uncertainty has no structure tying nearby items together. A new user would get exploration that is spread item by item rather than over regions of interest. We train an epinet head on the same two-tower model as a baseline. Interest-wise Coverage within twenty rounds is the metric that would show whether correlated uncertainty matters.
Why not just run TaNP and then apply an MMR or SOG diversity reranker? This is cheap and plausible. Reranking adds diversity without regard to whether it is informative, and the NDCG drop from 0.921 to 0.899 under SOG shows what untargeted diversity costs. We run TaNP followed by SOG-style reranking as a baseline. If it reaches our early-bubble index at equal hit rate, the targeted acquisition is unnecessary.
Decisive Checks
Three results settle the proposal. First, at matched cumulative hit rate over twenty rounds, deviation-variance UCB must show a lower early-bubble index and higher Interest-wise Coverage than total-variance UCB, the exact-GP-with-population-mean variant, and TaNP plus reranking. If it does not, the core claim fails. Second, catalog-coverage inducing points must outperform density-driven placement on hit rate for held-out niche clusters. This would be the recommendation-side counterpart of the over-smoothing finding of Maus et al. Third, per-interaction update cost must stay flat as history grows to thousands of interactions, while exact GPR4DUR's cost grows cubically, with no loss in warm-user NDCG.
References
- Density-based User Representation using Gaussian Process Regression for Multi-interest Personalized Retrieval
- Hierarchical Inducing Point Gaussian Process for Inter-domian Observations
- Approximation-Aware Bayesian Optimization
- Tucker Gaussian Process for Regression and Collaborative Filtering
- Collaborative Learning in Kernel-Based Bandits for Distributed Users
- Recurrent Memory for Online Interdomain Gaussian Processes
- Task-adaptive Neural Process for User Cold-Start Recommendation
- How does serendipity affect diversity in recommender systems? A serendipity-oriented greedy algorithm
- Epinet for Content Cold Start