Freshness as the Price of Exploration: Deterring Free Riders in Drifting Recommender Networks

When many users or devices learn which items are good by sharing what they observe, someone has to try the uncertain options. That trying, called exploration, costs the person who does it: they see worse recommendations and may leave the service. A known result shows that a selfish participant who simply watches others explore can learn almost for free. Its regret, the reward lost relative to always picking the best option, stays bounded by a constant, while the participants doing the exploring pay a cost that grows logarithmically over time (Quantifying the Burden of Exploration and the Unfairness of Free Riding). That result assumes tastes never change. In real recommendation, tastes drift, so exploration becomes a recurring cost rather than a one-time one. The same drift also makes information perishable. Knowing what was good last month is worth less than knowing what is good now.

This note proposes using that perishability as the incentive. A sharing platform can give contributors the pooled exploration data immediately and give non-contributors the same data after a delay. Under stationary tastes, a delay costs a free rider almost nothing. Under drift, every change in tastes the free rider learns about late costs it real reward. The delay therefore works as a price that needs no money, no payments contract and no honest-cost reporting. It also gives brand-new users, the cold-start case, a stale but useful starting point while they have nothing to contribute yet. We claim, and will test, that a delay chosen to match the measured drift rate makes contributing to exploration the self-interested choice for a broad range of drift rates. We also claim it keeps more welfare for newcomers than simply excluding non-contributors.

Core Claim

Consider $N$ agents. Each runs a recommendation policy for one user, or for a group of users on one device. Each can upload its interaction statistics to a shared pool. An agent "contributes" in a round if it serves an exploration item the platform assigns and uploads the outcome. The platform can check this, because it logs which items were served and whether they were clicked. Rewards follow a piecewise-stationary process: preferences hold steady between $S$ change points over a horizon of $T$ rounds. Non-contributors see pooled statistics delayed by $d$ rounds.

A free rider learns of each change $d$ rounds late, plus a detection lag. During that window it plays an arm that is now suboptimal by some gap $\Delta$. Its regret is therefore at least on the order of

$$R_{\text{free}}(d) \gtrsim S \cdot d \cdot \Delta,$$

where the form simply counts $S$ changes, each costing about $d$ rounds of lost reward $\Delta$. A contributor gets fresh data but pays a per-round exploration cost. Write the total of that cost over the horizon as $C_{\text{explore}}(T)$, which includes the extra risk of user departure that Modeling Attrition in Recommender Systems with Departing Bandits shows attaches to poor exploratory recommendations. Contributing is the best response whenever

$$C_{\text{explore}}(T) < S \cdot d \cdot \Delta - R_{\text{fresh}},$$

where $R_{\text{fresh}}$ is the regret a contributor still incurs with fresh shared data.

The design problem is to pick the smallest $d$ that satisfies this inequality for the drift actually observed. A smaller delay keeps the most value for newcomers and for honest non-contributors, such as low-battery devices. The inequality also shows where the idea fails. When drift is slow ($S$ small), no reasonable delay deters free riding, and the proposal must say so rather than hide it.

Relation to Prior Work

Three papers motivate the gap. The free-riding analysis in Quantifying the Burden of Exploration and the Unfairness of Free Riding gives algorithms (SampleAugmentingMeanGreedy, CountGreedy and UCBMeanGreedy) that achieve constant regret by watching a self-reliant agent. It assumes static rewards and an exploited agent that does nothing in response. We keep its free-rider algorithms as the adversary and change both assumptions. Parallel Online Clustering of Bandits via Hedonic Game (CLUB-HG) lets data-poor new users borrow observations from a cluster formed as a coalition game. It treats players as cooperative and preferences as fixed, and its authors name dynamic preferences as open. We study what happens in that borrowing step when players are selfish and preferences move. Federated Continual Recommendation (F³CRec) tracks preference shift on devices by comparing top-N ranking discrepancies between consecutive time blocks. It assumes every client participates faithfully. We reuse its drift measurement to calibrate the delay.

Two papers supply contrasting mechanisms that constrain the design. FACT or Fiction: Can Truthful Mechanisms Eliminate Federated Free Riding? makes truthful cost reporting a dominant strategy through penalties, a three-player "sandwich" comparison of reported costs and decoupled rewards. It relies on an honest server, monetary-style transfers, independent data with no drift, and no collusion. Our mechanism needs no cost reports and no transfers. It only needs observable serving actions. On the other hand, it is weaker when drift is slow, which FACT does not depend on. The reputation line in wireless networks, CORE (Refik Molva) and graded retaliation with recovery (Yan Lü), conditions service on past cooperation. Our delay is a graded, information-based version of that conditioning. Like "Gradual," it allows recovery, because an agent that resumes contributing gets fresh data again immediately.

Research Program

The first piece is analytical. We will extend the free-rider bounds to piecewise-stationary rewards. Self-reliant agents will run a sliding-window or restart-based upper-confidence-bound policy; such a policy picks the arm with the highest optimistic estimate and forgets old data. We will derive the regret of CountGreedy-style and UCBMeanGreedy-style free riders as a function of $S$, $d$ and the explorer's window length. The aim is to make the lower bound above precise, including the detection lag that exists even when $d = 0$. That lag matters: drift alone already shrinks the free-rider advantage somewhat, and we need to know how much before crediting the delay.

The second piece is the mechanism. The platform estimates drift online with the F³CRec-style ranking-discrepancy statistic on pooled data, converts it to an estimate of $S/T$, and sets $d$ to the smallest value satisfying the incentive inequality. It adds a margin for estimation error. A newcomer with no history receives the delayed pool from day one. The delayed pool is a warm prior that cold-start methods such as CLUB-HG would otherwise give for free. The newcomer gets fresh access once it begins contributing.

The third piece is behavioral. Agents are learning best-responders that choose each epoch whether to contribute, based on realized utility, including churn of their user under a departure model. We will measure the equilibrium contribution rate, total welfare, and the welfare of newcomers and resource-limited agents.

Baselines

The naive reference is no sharing: each agent runs its own sliding-window bandit. This bounds what pooling must beat. The cooperative ceiling is full sharing with fully altruistic agents, the setting implicitly assumed by F³CRec and CLUB-HG. This bounds achievable welfare. The failure case is full sharing with selfish agents running the free-rider algorithms from the burden-of-exploration paper. Over learning rounds, this should collapse toward few contributors. For that paper, the file reports only the qualitative result that free-rider regret flattens to a constant while explorers' regret grows logarithmically. It reports no reported result found on Lacuna for free riding under drift.

The strongest existing competitor for cold-start borrowing is CLUB-HG with a sliding window added. It is the only method in the file in which newcomers borrow peers' exploration through a stable coalition structure, and it reports recovering the true 10 clusters on its Netflix setup where CLUB fragments into up to 60. The strongest competitor for incentives is a FACT-style penalty, adapted so that clients below a contribution benchmark pay a utility penalty. FACT reports a 66% loss reduction for resource-constrained hospitals versus isolated training on HAM10000. There is no reported result found on Lacuna for FACT in drifting or bandit settings. For the drift-tracking component on recommendation streams, F³CRec reports 4% to 50% relative gains over Reg and KD on ML-100K, ML-Latest-Small, Lastfm-2K and HetRec2011.

All methods will use the same data streams, the same base bandit learner, the same communication rounds and the same hyperparameter search budget per method. Penalty magnitudes for the FACT-style baseline will be tuned as carefully as our delay.

Two ablations isolate the key ingredient. The first, binary exclusion, gives non-contributors no pooled data at all. The second, a fixed delay, uses a delay that is not calibrated to drift. Beating the field means two things. First, a higher equilibrium contribution rate and higher total welfare than selfish full sharing and the FACT-style penalty, at matched drift levels. Second, newcomer regret over the first 100 rounds at least as good as binary exclusion's contributor-equivalent outcome, while beating exclusion on total welfare.

Why not just…?

Why not just exclude non-contributors entirely? This is the most serious threat, because exclusion is the simplest strong incentive. It fails two groups the delay is meant to serve. Newcomers have nothing to contribute yet, and devices may be throttled by battery for reasons other than strategy. The battery case is the misclassification problem raised against CORE-style reputation. If our experiments show exclusion matches the delay on total welfare and newcomer regret, the honest conclusion is that graded delay adds nothing. The exclusion ablation is designed to show this directly.

Why not just pay contributors, as FACT does? Payments need a trusted server, a currency, and either honest cost reports or the sandwich competition. FACT's guarantees are proved for static, independent data and assume no collusion. A delay needs none of this and is hard to collude around, because freshness cannot be pooled among free riders who do not explore. Payments do work at slow drift, where our mechanism does not. We will report the drift rate at which the two cross over rather than claim dominance.

Why not just let drift handle it, since stale counts already hurt free riders? Drift alone does add a detection lag for free riders. If that lag already makes free riding unprofitable, the mechanism is unnecessary. The analytical bound at $d = 0$ and the "selfish full sharing" baseline measure exactly this. The proposal survives only if free riders remain profitable at $d = 0$ over a meaningful range of drift.

Proposed Experiments

Synthetic tests extend the burden-of-exploration setups, 10-arm Bernoulli bandits and linear bandits with 50 players and 30 arms, to piecewise-stationary rewards. They sweep the number of change points $S$ and the departure probability following the departing-bandits model. These tests verify the predicted threshold: contribution should become the best response once $d$ exceeds roughly $C_{\text{explore}}/(S\Delta)$. Real streams come from MovieLens 25M and the Netflix 200-user setup used by CLUB-HG, with timestamps restored to induce real drift. We also use the four-block chronological splits of ML-100K, Lastfm-2K and HetRec2011 from F³CRec, and the eight-year New Yorker caption ranking data as a long-horizon crowd-preference drift test. Metrics are per-agent cumulative regret, the free-rider advantage ratio, the equilibrium contribution rate, total welfare, newcomer regret over the first k rounds, and the user-departure rate.

The decisive check is a phase diagram over drift rate and delay. The proposal is supported if a region exists where calibrated delay sustains contribution and beats both exclusion and penalties on welfare. It is refuted if that region is empty or coincides with the region where drift alone already deters free riding.