Recommendation and matching systems have to keep exploring, because what users want changes over time. The standard tool for neural exploration scores each candidate by how unfamiliar its gradient looks compared with the gradients the system has already learned from. This score never forgets. As history piles up, the system becomes confident everywhere and stops exploring just when the user's taste moves. The usual fix is to discount old data uniformly, which throws away everything, including facts that never change. Some facts are durable by construction: cheaper is never worse, and higher quality is never worse. Where those relationships hold, they can be written directly into the network as monotonicity constraints.
This note proposes using that architectural split to decide what the exploration machinery remembers. A partially monotone reward model routes "durable direction" features and "free" features through separate parameter blocks. We keep two uncertainty memories over the gradients of those blocks. One forgets slowly or not at all and covers the monotone block. The other forgets quickly and covers the free block, where drift is allowed. On a large item graph, the graph network is run once per refresh with a scalable message-passing scheme, and exploration operates only on a small reward head. The cost of the uncertainty computation therefore does not grow with graph size. The bet is that this split explores less wastefully than uniform discounting when drift is confined to the free part of preferences, and adapts faster than no discounting.
Core Claim
Neural Contextual Bandits with UCB-based Exploration supplies the method. NeuralUCB is a bandit algorithm that treats the network's parameter gradient $g(x)$ as a feature vector. It accumulates a covariance $\Sigma$ of past gradients and adds the bonus $\beta\sqrt{g(x)^\top \Sigma^{-1} g(x)}$ to the predicted reward. The file notes that $\Sigma$ only accumulates, so the bonus decays and the method fails under drift. Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift motivates the uniform-discount alternative: NS-DPO weights each preference by $\gamma^{T-t_i-1}$. The file names two problems with that scheme: it needs the rate of change known in advance, and it penalizes durable baseline preferences and abandoned whims equally.
Our claim is that a partially monotone architecture gives a principled, label-free partition of the gradient into a durable block $g_m(x)$ and a drifting block $g_f(x)$. The monotone parameters are positivity-reparameterized weights on features with known direction, as in the exponentiated and confluence units of Scalable Monotonic Neural Networks. We maintain
$$\Sigma_t = \lambda I + \sum_{s\le t} \mathrm{diag}\big(\gamma_m^{\,t-s} I_m,\ \gamma_f^{\,t-s} I_f\big)\odot\, g(x_s)g(x_s)^\top,$$
where $\gamma_m \approx 1$ is the slow forgetting rate on the monotone block, $\gamma_f < 1$ is the fast rate on the free block, $I_m$ and $I_f$ are the identity blocks for each parameter group, and $\odot$ applies the block-wise weights to the outer product. Cross-block terms use the geometric mean of the two rates. The sign constraint guarantees that the direction of a monotone effect cannot drift. Its magnitude can, so we also run a residual-based change test on the monotone block that resets its memory when it fires. That reset is what keeps the scheme honest when the durability assumption fails.
The closest existing work is Bayesian Optimization with Preference Exploration using a Monotonic Neural Network Ensemble, known as BOPE-MoNNE. It combines monotone networks with exploration, but it uses an 8-member ensemble rather than gradient uncertainty, assumes the user's utility is static, and works on 2–10 dimensional inputs. Our proposal differs on all three points. Its central object is something BOPE-MoNNE does not have: memory that forgets differently across constrained and unconstrained parameters.
Research Program
Model. Arms are nodes, such as items or jobs, in a large interaction graph. Node embeddings come from CFGNN, which uses shortest-path hub labels to split the graph into transit "core" nodes and local "fringe" nodes. It passes messages fringe-to-core and then core-to-fringe, which avoids exponential neighborhood growth. Embeddings are recomputed on a schedule rather than per round. When the topology itself changes, Adapting to Evolving Graphs supplies ACNR, an incremental coarsening method that may reassign nodes.
The reward head is a small SMNN. Its monotone inputs are attributes with known direction, such as discount or rating, and its free inputs are the graph embedding together with user context. Exploration gradients are taken only with respect to head parameters, so $p$ is in the thousands. This makes direct inversion of $\Sigma$ affordable, which addresses the file's covariance bottleneck.
This design deliberately departs from Graph Neural Network Bandits. That paper takes gradients through a single-layer graph network and obtains regret independent of the number of nodes $N$, but it gives no constraints and no handling of drift. We trade exploration through the graph encoder for scale. One ablation checks what that trade costs.
Optimization stability. Exponentiated weights $e^w$ make gradient scale unstable, so the gradient blocks are not on comparable scales. We normalize each block's gradient by a running norm before forming $\Sigma$. We also compare $e^w$ against the softplus reparameterization, because the bonus depends directly on gradient geometry.
Dominance pruning. Monotonicity permits a cheap extra step. When candidate A weakly dominates B on monotone features and ties on free features, B's upper bound can be capped at A's. This step is reported separately so it is not confused with the memory split.
Analysis. No neural tangent kernel theory exists for monotone architectures, and we do not claim one. We analyze only the linearized case: a linear bandit whose parameter drifts inside a known subspace with variation budget $B_f$, while the complementary subspace is fixed. We aim to show that block discounting removes the dependence on the fixed subspace's dimension from the drift term that uniform discounting pays. The reasoning is that uniform discounting re-explores every direction at rate $1-\gamma$, while block discounting re-explores only the drifting directions.
Baselines
The naive reference is stationary NeuralUCB on the same SMNN head, with no discounting. It shows the preference-inertia failure the proposal targets. Beating it during drift phases is required, but that alone proves little.
The strongest competitor is uniformly discounted NeuralUCB on the same monotone head. It applies one rate $\gamma$ to the whole covariance, the bandit analogue of NS-DPO's weighting, and $\gamma$ is tuned on a validation stream. It matches our system in every respect except the memory split, so it isolates the key ingredient. We give it the same tuning budget, a grid of eight values, that our method gets for the pair $(\gamma_m,\gamma_f)$ plus the change-test threshold.
We also run neural predictive ensemble sampling from Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Sampling, the main neural non-stationary alternative. We run Discounted Thompson Sampling over frozen embeddings, which is effectively a discounted Neural Linear Bandit. We run a monotone 8-member ensemble in the style of BOPE-MoNNE with discounted training weights. Every method uses the same embeddings, the same head architecture where applicable, and matched wall-clock compute per round.
Two ablations complete the set: an unconstrained head with uniform discounting, and our split with a random parameter partition of the same block sizes. Together they separate the effect of monotonicity from the effect of the split.
I found no reported result on Lacuna for any of these methods on a drifting graph-recommendation stream. Beating a baseline therefore means lower cumulative dynamic regret than the best-tuned uniform discount, with confidence intervals over at least ten seeds that do not overlap, on drift scenarios where drift is confined to the free block. Where drift touches the monotone block, we require regret no worse than uniform discounting.
Why not just…?
Why not just tune a single discount factor? This is the real threat. If the best uniform $\gamma$ is already close to the best $\gamma_f$ and the monotone block is small, the split will gain almost nothing. The controlled experiments vary the share of preference variance carried by the monotone block. The proposal predicts that the advantage grows with that share. If the advantage stays flat near zero across shares, the idea is wrong.
Why not just use ensembles with discounting, like MoNNE plus NS-DPO weights? Ensembles avoid inverting a covariance matrix and handle constraints naturally. They give no explicit handle on which directions to forget, and each member needs retraining every round, so they cost $K$ times more. BOPE-MoNNE also reports that Hamiltonian Monte Carlo sampling failed on pairwise data, which indicates that uncertainty for monotone preference models is fragile. Matched-compute comparison settles the question. If ensembles win at equal compute, we report that.
Why not just restart or use a sliding window when a change detector fires? Restarts are simple and need no prior knowledge of the rate of change. They also discard the durable knowledge, which is exactly what this proposal preserves. We include a detector-plus-full-restart baseline. Our method should beat it mainly in the recovery window after each change.
Proposed Experiments
The file names no specific graph benchmark, so we use two settings.
The controlled setting is a synthetic stream on a public-scale random graph with a known monotone ground-truth utility. Drift is injected in three ways: into free-block coefficients only, into monotone-block magnitudes, and into both. The mixing share and the variation budget are swept.
The semi-synthetic setting is a public timestamped user–item interaction graph. A reward oracle is fit per time window, and items carry price and rating attributes as monotone inputs. It is replayed as a bandit with an offline replay estimator.
Metrics are cumulative dynamic regret, regret within $k$ rounds after each change point, the rate of monotonicity violations on held-out pairs (zero by construction for constrained heads, measured for the unconstrained ablation), and per-round latency as graph size grows by orders of magnitude.
The decisive checks are three. First, under free-only drift, the split beats tuned uniform discounting and the random-partition ablation. Second, under monotone-magnitude drift, the change test keeps regret within the uniform baseline's confidence band. Third, per-round cost stays flat as node count grows, with CFGNN refresh time reported separately. Failing the first check kills the core claim. Failing the second confines the method to settings where the monotone effects are genuinely durable.
References
- Neural Contextual Bandits with UCB-based Exploration
- Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift
- Scalable Monotonic Neural Networks
- Bayesian Optimization with Preference Exploration using a Monotonic Neural Network Ensemble
- Bridging Indexing Structure and Graph Learning: Expressive and Scalable Graph Neural Network via Core-Fringe
- Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening
- Graph Neural Network Bandits
- Non-stationary Contextual Bandit Learning via Neural Predictive Ensemble Sampling
- Discounted Thompson Sampling for Non-Stationary Bandit Problems
- Long-Term Value of Exploration: Measurements, Findings and Algorithms