Several learners, such as hospitals, ad platforms or recommendation services, each repeatedly choose among the same set of options and learn from the outcomes. If they pool what they observe, each one learns faster. Most work on this kind of shared learning assumes every option pays the same to everyone. Under that assumption, pooling is costly for the contributor: to supply useful data you must try options that are bad for you. That is why the one incentive-aware method for this setting pays agents money for exploring and charges them for using shared data. It only breaks even with thousands of participants. When different learners prefer different options, the picture changes. Each learner's favorite option is something it plays constantly at no cost to itself, and every play produces data that others need. Each agent therefore has something valuable to trade that costs it nothing to produce.
We propose to turn that observation into a mechanism. Agents earn access to the shared pool by contributing observations of their own favorite options, and the credit for each contribution is weighted by how much it saves the receivers. A light spot-checking rule catches fabricated reports. Where some options are nobody's favorite, the unavoidable exploration of those options is split by a bargaining rule. Each agent's fallback in that bargaining is what it would achieve learning alone, which differs from agent to agent. The claim is that preference diversity makes incentive compatibility cheap. We aim to show that every agent does no worse than learning alone, that honest sharing is an approximate equilibrium, and that no money changes hands. When every option is someone's favorite, near-constant group regret is kept.
Core Claim
The setting is the multi-agent bandit with heterogeneous rewards (a bandit is a repeated choice among options, called arms, whose payoffs must be learned) from Exploration for Free. That paper models agent $m$'s expected reward on arm $k$ as $r_{m,k} = u_k + v_{m,k}$. Here $u_k$ is a quality shared by all agents and $v_{m,k}$ is a preference known only to agent $m$. Its FreeExp algorithm has each agent broadcast samples of $u_k$ from its current best arm, which the paper calls its "pivot." The paper proves that group regret falls from logarithmic to constant when every arm is someone's pivot. The whole result assumes agents broadcast honestly and take on assigned exploration with no compensation.
The closest incentive-aware work is Balanced-ETC in Balanced and Incentivized Learning with Limited Shared Information. It enforces individual rationality, meaning no agent does worse than playing alone, through monetary compensations and fees benchmarked against a single-player UCB baseline. It explicitly assumes homogeneous rewards, and its platform runs at a deficit until roughly 4,000 agents.
Our claim is that under heterogeneous rewards, individual rationality and approximate truthfulness can be enforced without transfers. The mechanism has three parts. First, access to pooled samples is gated by a credit ledger. Second, credit is denominated in receiver-weighted pivot observations. Third, monetary compensation from Balanced-ETC is replaced by a bargaining allocation of the residual, genuinely costly exploration. Writing $R_m^{\text{solo}}(T)$ for agent $m$'s expected regret over $T$ rounds under KL-UCB alone, the target guarantee for every honest agent is
$$R_m^{\text{mech}}(T) \le R_m^{\text{solo}}(T), \qquad R_m^{\text{solo}}(T) \approx \sum_{k \ne k_m^*} \frac{\Delta_{m,k}\,\log T}{\mathrm{kl}(r_{m,k}, r_{m,k_m^*})},$$
where $k_m^*$ is agent $m$'s best arm, $\Delta_{m,k}$ its gap on arm $k$, and $\mathrm{kl}$ the Bernoulli divergence. The right-hand form is the standard asymptotic lower-bound rate. It also tells us how much a sample of arm $k$ is worth to agent $m$: roughly the fraction of the required $\log T/\mathrm{kl}$ pulls it replaces. That is the weight used for credit. The ledger enforces that the information agent $m$ receives is bounded by a constant multiple of the value it contributes, plus a small unconditional allowance.
Research Program
The first component is the mechanism itself, built on FreeExp's pivot-tracking KL-UCB. Each broadcast of a $u_k$ sample earns credit equal to its value to the receivers who have not yet resolved arm $k$. A receiver's use of the pool is released with a lag, or thinned, when its credit is negative. We use lags rather than corruption because controlled delay of intermediate results is the non-monetary lever in How to Incentivize Data-Driven Collaboration Among Competing Parties. It also degrades a defector's performance gracefully toward, but not below, its solo baseline.
Arms that are nobody's pivot must still be explored at real cost. For these we replace FreeExp's implicit burden-sharing with a Nash bargaining split in the style of Fair Exploration via Axiomatic Bargaining, which maximizes the product of groups' regret savings relative to going alone. We depart from that paper in two ways: each agent's disagreement point is its own heterogeneous $R_m^{\text{solo}}$, and the agents are strategic rather than passive cohorts.
The second component addresses fabrication. Collaborative Mean Estimation Among Heterogeneous Strategic Agents cross-validates submissions against peer consensus and corrupts a cheater's returned estimate. It notes that an agent who is the sole source for a quantity has "leverage" and cannot be cross-checked. In our setting that is the agent who alone pivots on an arm. We handle it with randomized spot checks: receivers occasionally pull a reported arm themselves, at a cost we bound as a fraction of the saved exploration. Once other sources accumulate, we run a delayed sequential consistency test. Detected deviation forfeits credit.
The third component is analysis. We aim to prove three things. First, individual rationality in the form above. Second, that truthful broadcasting and accepting one's assigned residual exploration form an $\epsilon$-Nash equilibrium, with $\epsilon$ controlled by the spot-check rate. Third, that group regret remains $O(1)$ under full pivot coverage and becomes $O(|\mathcal{U}|\log T)$ otherwise, where $\mathcal{U}$ is the set of uncovered arms. We will also bound the price of stability, the efficiency lost relative to altruistic FreeExp. Existing $\Omega(\sqrt{m})$ lower bounds for static collaboration, from One for One, or All for All and the mean-estimation paper, suggest such a loss is unavoidable in general. Our conjecture is that the loss is confined to the uncovered arms, because contributions on covered arms are free.
Finally, we address privacy of preferences. Broadcasting $u_k$ samples from one's pivot reveals which arm one favors. Bayesian Exploration with Heterogeneous Agents shows that hiding types from a central recommender pushes regret from constant to logarithmic. In our peer-to-peer model each agent knows its own $v_{m,k}$ and reports only $u_k$, so we predict the constant-regret regime survives. We will test whether hiding pivot identities, rather than preference values, is what triggers that degradation.
Baselines
The naive reference point is every agent running KL-UCB alone. This defines each agent's outside option and is the quantity our individual-rationality claim is measured against. Beating it means every single agent's regret lies below its solo regret across seeds, not just the average.
The strongest efficiency competitor is FreeExp from Exploration for Free under full compliance. Its paper reports only that it "significantly outperformed" CO-UCB on the Avito click data and that regret flattened when all arms were covered. No numeric regret value was found on Lacuna for FreeExp on Avito. Compliant FreeExp is an upper bound we do not expect to beat on group regret. Success means staying within a small constant factor of it while remaining stable when agents are allowed to best-respond. We will also run FreeExp with best-responding agents; beating that is the real test.
The strongest incentive-aware competitor is Balanced-ETC with its compensation and cost accounting from Balanced and Incentivized Learning with Limited Shared Information. We port it to heterogeneous rewards by giving each agent its own solo baseline and disabling global elimination, since that step is ill-defined without a shared ranking. Its reported results are that the incentive layer brought maximum individual regret below the single-player 2-UCB baseline in a 10-arm, $T=10^6$ simulation, and that the platform became profitable at roughly 4,000 agents. Beating it means matching individual rationality with zero transfers, and doing so at agent counts in the tens to hundreds where Balanced-ETC runs a deficit.
The key ablation replaces value-weighted credit with raw sample counts, a tit-for-tat rule. This isolates whether pricing information by receivers' personalized gaps matters. A second ablation removes spot checks, isolating the contribution of fabrication resistance.
All methods share environments, horizons, seeds and a common hyperparameter search budget over their confidence and threshold parameters.
Why not just…?
Why not just have everyone learn alone? Solo learning is automatically individually rational, but it forfeits the collective gain. Each agent pays the full $\Omega(\log T)$ exploration cost, where cooperation under full coverage achieves constant group regret Exploration for Free. It stays in every experiment as the reference point, and we report the fraction of the cooperative gain our mechanism retains.
Why not just run FreeExp and trust agents, since sharing pivot data is free anyway? This is the most serious threat, and we treat it as an empirical question, not a strawman. If withholding and fabrication yield negligible gains, the mechanism is unnecessary. However, only broadcasting on covered arms is free. FreeExp also requires agents to explore uncovered arms at real cost, and a rational agent can skip that and wait for others. That is the free-riding pattern documented in federated learning, where an agent cutting its data to 25% still met its accuracy target 94% of the time under plain averaging One for One, or All for All. We will compute best-response deviation gains under FreeExp as coverage varies. We expect them to be near zero at full coverage and to grow with the number of uncovered arms. If they stay near zero throughout, we will report that the problem is simpler than claimed.
Why not just port Balanced-ETC's payments with personalized baselines? It is feasible, and it is our main incentive-aware baseline. But it needs a platform able to make transfers, which competing hospitals or ad consortia often cannot do. Its reported solvency threshold of roughly 4,000 agents also rules out small consortia. The solvency-versus-population experiment below settles whether transfer-free gating matches its individual-rationality guarantee at small scale.
Why not just use simple reciprocity, sharing only with those who share? This is our count-based ablation. Its weakness is that under heterogeneity a sample of an arm is worth almost nothing to an agent with a large gap and a lot to one near indifference. Counting samples therefore misprices contributions and can violate individual rationality for agents whose pivots are of little value to others. If the ablation performs as well as value weighting, we will adopt the simpler rule.
Proposed Experiments
We use three environments. The first is the Avito ad-click setting from Exploration for Free, reconstructed with agents as user segments and pivot coverage varied from none to full. The second is the 10-arm synthetic environment of Balanced-ETC, with rewards from 0.9 to 0.0 and $T=10^6$, extended with preference offsets $v_{m,k}$ of controlled magnitude so that the homogeneous case is the zero-offset endpoint. The third is the Warfarin dosing data (5,700 patients) used by Fair Exploration via Axiomatic Bargaining, with race and age cohorts treated as agents whose best dose genuinely differs. For the synthetic environment we will also sweep agent counts from 5 to 5,000.
The metrics are group regret, the maximum over agents of the ratio of mechanism regret to solo regret, best-response deviation gain (computed by searching over withholding, fabrication and skipping residual exploration), fabrication detection delay, platform net transfer (always zero for ours), and messages per round.
Three checks would decide the proposal. First, under full coverage, FreeExp's best-response deviation gain should be small and our mechanism should match compliant FreeExp. Under partial coverage, deviation gains under FreeExp should grow while ours stay below the spot-check-controlled $\epsilon$. Second, the maximum regret ratio should stay below one for every agent at agent counts where ported Balanced-ETC runs a deficit. Third, as the preference offsets shrink to zero, our mechanism's advantage should vanish. If it did not vanish, something other than free pivot data would be driving the gains.
References
- Exploration for Free: How Does Reward Heterogeneity Improve Regret in Cooperative Multi-agent Bandits?
- Balanced and Incentivized Learning with Limited Shared Information in Multi-agent Multi-armed Bandit
- How to Incentivize Data-Driven Collaboration Among Competing Parties
- Fair Exploration via Axiomatic Bargaining
- Collaborative Mean Estimation Among Heterogeneous Strategic Agents: Individual Rationality, Fairness, and Truthful Contribution
- One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning
- Bayesian Exploration with Heterogeneous Agents