Tracking the Set of Good Options When Tastes Drift

Many systems have to return a set of acceptable options rather than a single winner: the captions worth showing a judge, the videos worth putting in a feed, the safety rules worth checking for a given prompt. Two lines of research each handle half of this problem. The first stops fixing the set size in advance. It returns every option within a margin $\epsilon$ of the best one, so the set grows when many options are good and shrinks when few are. The second accepts that human preferences change over time and discounts old feedback. The two lines have not been combined. The methods that adapt set size assume options keep constant quality. The methods that handle drift output a fixed number of items, often exactly two, as in pairwise preference learning.

The obvious way to combine them is to wrap a set-finding algorithm in a sliding window and forget old data. That discards a great deal of information for no good reason. Much real preference drift is common-mode: a user who is tired, satiated, or in a different mood rates everything lower, and the ranking among options barely moves. A set defined relative to the best option is unaffected by common-mode shifts, so a method that forgets everything when overall levels move pays a sampling cost it does not need to pay. This note proposes to estimate differences between options with long memory and the overall level with short memory. It also proposes to use changes in which items belong to the set, rather than changes in raw reward, as the signal that relative preferences have actually drifted.

Core Claim

Write the mean reward of option $i$ at time $t$ as $\mu_i(t) = c(t) + g_i(t)$. Here $c(t)$ is a shared level that moves with the user's state, and $g_i(t)$ is the option's relative quality. The additive good set is

$$G_t = \{\, i : g_i(t) > \max_j g_j(t) - \epsilon \,\},$$

which does not depend on $c(t)$ at all. For the multiplicative version of the margin, the same holds for common multiplicative shifts once rewards are compared as ratios.

The claim has two parts. First, an estimator that cancels $c(t)$ needs an amount of memory set by the drift in the gaps $g_i$, not by the drift in the overall reward. Within-slate differences, time-local paired differences, or direct pairwise comparisons all cancel $c(t)$. Second, when common-mode drift makes up most of the total drift, this estimator tracks $G_t$ with fewer samples and less lag than any single-timescale forgetting scheme. When relative drift dominates, it should fall back to matching sliding-window methods. That fallback is the honest ceiling on what we expect to gain, and it is testable.

Relation to Prior Work

The method builds on the relative-bar formulation of Finding All ε-Good Arms in Stochastic Bandits. That paper defines the problem of returning every arm within $\epsilon$ of the best and gives algorithms whose returned set adapts to instance quality: on New Yorker caption-contest data the returned set ranged from 27 to 748 good captions. Its algorithms FAREAST and (ST)² assume stationary arm means, and it also shows that verifying membership for arms sitting exactly on the threshold needs unbounded samples. Under drift, arms will cross the threshold routinely, so this boundary problem becomes the normal case. We handle it by reporting an explicit "uncertain" band with hysteresis rather than by assuming a fixed slack.

Top-k Selection based on Adaptive Sampling of Noisy Preferences motivates the setting: it argues that fixed quotas fail when candidate quality varies. Yet its racing algorithms still require $k$ in advance and assume fixed pairwise win probabilities. We keep its idea of pairwise feedback but drop both assumptions.

On the drift side, Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift supplies the discounting technique. It weights each preference pair by $\gamma^{T-t_i-1}$ and proves dynamic-regret guarantees. It also leaves two gaps that we target directly. Choosing $\gamma$ requires knowing the drift budget, and a uniform time decay cannot tell lasting feedback from obsolete feedback. Our two-timescale split is a structured answer to the second gap. Choosing the window for the gaps by consistency checks across window lengths answers the first.

Three papers constrain the design and show where the intersection is only partly covered. Dynamic Adaptation to Preference Drift in Interactive Evolutionary Multi-Objective Optimization adapts the number of active objectives under drifting decision-maker weights and purges conflicting history on detected change. It does not adapt the set of items shown, and it relies on linear univariate screening. Ads that Stick chooses the optimal ad count under satiation and annoyance decay, but its items are homogeneous and its user memory parameter is fixed and known. HiGR generates slates with preference alignment but keeps the slate length fixed (it is evaluated at NDCG@5) and aligns on stationary logs.

Research Program

We will build a tracking algorithm with three parts.

The first part is a gap estimator. It forms reward differences only between observations that share, or nearly share, the common level $c(t)$. Three sources qualify: items shown in the same slate, pulls close together in time relative to a reference arm, or native pairwise comparisons. These differences are fed to per-pair confidence bounds.

The second part is an adaptive memory rule. Each gap is estimated over several nested windows, and we use the longest window whose estimate agrees with the shorter ones within confidence. This rule needs no variation budget. A separate fast-forgetting estimate of $c(t)$ is kept only for the multiplicative margin and for reporting.

The third part is a membership monitor. It flags drift when an item's confidence interval moves from clearly-in to clearly-out of $G_t$ or the reverse, and it shortens memory only for gaps involving that item. This is the "per-item forgetting" that time-uniform discounting cannot express.

Sampling follows FAREAST's structure of a good filter plus a bad filter, run continuously rather than to termination. Arms near the boundary are re-sampled in proportion to how recently their membership was uncertain.

On the analysis side, we aim for a tracking-error bound in which drift in $c(t)$ does not appear and only the variation budget of the gaps enters. The comparison bound for single-timescale sliding windows depends on total variation. Proving the gap-only dependence is a stated goal, not a promise. At minimum we will characterize empirically how tracking error scales with the two budgets separately.

Baselines

The naive reference point is a drift-aware top-$k$ with fixed $k$. It is a discounted UCB ranking that returns the top $k$ items, with $k$ tuned on a held-out drift segment. It shows what abandoning fixed cardinality buys at all.

The strongest direct competitor is FAREAST from Finding All ε-Good Arms in Stochastic Bandits, run on absolute rewards in two variants. The first restarts on a CUSUM-style change detector applied to raw rewards. The second is a discounted version with weights $\gamma^{T-t}$ in the style of NS-DPO. For the second variant we sweep $\gamma$ over the same grid and give it an oracle-tuned $\gamma$ in a separate row, so it gets every advantage we can hand it.

We also include a reset strategy modeled on the "dynamic" purge of Dynamic Adaptation to Preference Drift in Interactive Evolutionary Multi-Objective Optimization. It discards historical observations that conflict with the latest ones.

For pairwise-feedback settings, the strongest competitor is a discounted Bradley–Terry model with thresholding. This is effectively NS-DPO's estimator used to define a relative set.

All methods receive identical feedback streams, sampling budgets, and hyperparameter grids, with the same number of tuning runs each.

The key ablation is our method with a single shared timescale for level and gaps. It isolates the decomposition. A second ablation removes membership-triggered per-item forgetting, which isolates the monitor.

There is no reported result on Lacuna for any method on drifting all-ε-good tracking, so the comparison numbers will be ours. The closest reported figures sit in neighboring settings. Right Now, Wrong Then reports a length-controlled win rate of 8.93 for NS-DPO against 7.29 for stationary DPO on non-stationary UltraFeedback. The objective-reduction paper reports more than 60% savings in objective evaluations.

Beating the strongest baseline means two things. First, lower time-averaged symmetric-difference error between the returned set and $G_t$ at equal sample budget, with non-overlapping bootstrap intervals, in the regimes dominated by common-mode drift. Second, no statistically meaningful loss in regimes dominated by relative drift.

Why not just…?

Why not just run a sliding window over absolute rewards and threshold? This is the most natural competitor, and it is the discounted-FAREAST baseline. Its weakness is structural: any window short enough to follow a fast shift in overall level also throws away gap information that is still valid. Because $G_t$ does not depend on $c(t)$, that discarded information was never stale. The synthetic sweep below makes this concrete by varying the common-mode budget while holding the relative budget fixed. If the sliding window keeps up with us even when common-mode drift is large, the decomposition is not worth its complexity, and we will report that.

Why not just restart a stationary good-set algorithm whenever a change detector fires? A detector on raw rewards fires on level shifts that leave the set unchanged, causing needless restarts. A detector that fires rarely lags on real membership changes. The restart baseline and the membership-monitor ablation measure exactly this trade-off, through false-restart counts and time-to-recover after a true membership change.

Why not just learn to predict the set size directly? One could train a cardinality head, as in Joint Learning of Set Cardinality and State Distribution, on logged data and output the top-$\hat{k}$. Such models learn a cardinality distribution from identically distributed training data, and the research file lists that stationarity assumption as their known limitation. They also provide no per-item confidence. We include a periodically retrained version on KuaiRec as a secondary baseline. If it matches us, that would suggest learned priors beat online tracking at KuaiRec's drift rates.

Why not just use discounted pairwise preferences, since pairwise comparisons already cancel the common level? This alternative is a real threat. Under Bradley–Terry feedback, common-mode drift cancels for free, and NS-DPO-style discounting of pairwise data is close to our method's pairwise instance. Our claimed gain in that regime is therefore narrower: it comes only from choosing memory per gap without a known drift budget and from per-item forgetting. The main advantage is expected with absolute feedback such as watch time or ratings, where cancellation must be constructed. We will report the two feedback types separately so a win in one cannot hide a tie in the other.

Proposed Experiments

The first experiment is synthetic and controlled. Arm configurations are drawn to mimic the spread of good-set sizes reported on caption data, from tens to hundreds of good arms. Drift is injected with separately controlled common-mode and relative variation budgets. Some changes are abrupt and some gradual, following the sudden and gradual shift protocols of NS-DPO. Because $G_t$ is known exactly, set-tracking error, lag after a membership change, samples used, and the fraction of arms reported as uncertain can all be measured precisely. The decisive check is the shape of the error surface over the two budgets. Our method's error should be roughly flat in the common-mode budget, and the single-timescale ablation's should rise with it.

The second experiment uses KuaiRec. Its small matrix is nearly fully observed: 1,411 users, 3,327 items, and 99.6% density. So every item's watch ratio for a user is known, and the true ε-good set can be computed for any slate without counterfactual guesswork. We order each user's interactions within the 15-day collection window, show variable-length slates, and reveal ground-truth watch ratios as feedback.

Before running any bandit, we will decompose the observed per-user drift into a shared level and item-relative components. This decomposition is itself a decisive check on the premise. If common-mode variance is a small share of total drift on KuaiRec, we will say that the method's motivating regime is rare in this data and present the synthetic results as the main evidence. If per-interaction ordering turns out to be too coarse for a meaningful drift analysis, KuaiRec reverts to a semi-synthetic role: its dense means serve as the base configuration, and drift is injected on top. Outcome metrics are set-tracking error against the watch-ratio ε-good set, cumulative watch ratio of shown slates, and the slate-length distribution over time. The length distribution directly tests whether sets shrink and grow as satiation sets in.

The third experiment, with pairwise feedback, uses the non-stationary UltraFeedback setup from Right Now, Wrong Then. The task is to track the set of responses within $\epsilon$ of the currently preferred one, compared against discounted Bradley–Terry thresholding. We expect at best a modest gain here and report it as the stress test of the fourth alternative above.

The proposal succeeds if the decomposition yields a clear, repeatable reduction in tracking error wherever common-mode drift is substantial, and it degrades gracefully to sliding-window performance elsewhere.