CS Paper Radar

Learning from a Mixture of Information Sources

Nicole Immorlica, Brendan Lucier, Yaroslav Mukhin, Clayton Thomas, Ruqing Xu

cs.GT econ.TH ·submitted 2026-09-27 04:54 UTC · v1

Abstract

We often learn from multiple sources that convey information in different ways. How informative is it to know the source of a signal, and how is this informativeness shaped by the distribution of sources? We extend the standard (binary-state, binary-signal) Blackwell experiment model by introducing a commonly known distribution over signaling schemes, representing the distribution of information sources. We compare learning under two information models: source-aware, where decision makers observe a signaling scheme and its realization (e.g., raw reviews, search results), and source-blind, where only the signal realization is observed (e.g., aggregate ratings, LLM-generated summaries). We show that a mean-preserving spread in the distribution of signaling schemes translates into Blackwell dominance for source-aware decision makers, implying they are "risk-loving" in information sources. In contrast, it has no impact on source-blind decision makers. When learning from repeated draws of signaling schemes, source-blind decision makers learn more slowly. However, as long as the average signaling scheme is $\varepsilon$ away from being completely uninformative, source-blind learning can match source-aware learning by using at most $O(1/\varepsilon)$ times more data.

Comment
Extended abstract to appear in WINE 2026 (The Conference on Web and Internet Economics)

Closest papers

Nearest neighbours by meaning across the whole index.

Truth Revelation, Information Hiding, or Misinformation: Characterization of Equilibrium Outcomes in Signaling Games

cs.GT cs.ITmath.OC ·2026-08-25 ·Ertan Kazıklı, Sinan Gezici, Serdar Yüksel
similarity 0.62
Abstract · 18 pages and 4 figures

In signaling games where a sender and a receiver have misaligned criteria, equilibrium behavior may lead to fully revealing, quantized, or randomized policies. Notably, the first arises in statistical decision theory and classical communication theoretic problems involving a fully aligned sensor and receiver, the second arises in Nash theoretic simultaneous signaling games, and the last may appear in Stackelberg type (leader-follower) Bayesian signaling games. In this paper, we investigate the Bayesian persuasion problem involving a receiver that tries to estimate the source. We show that for certain payoff structures, the equilibrium solution is such that a source observation is mapped to distinct messages with nonzero probabilities. More specifically, we completely characterize conditions under which the sender requires randomization for the Bayesian persuasion problem involving general sources with finite cardinality. In particular, regardless of whether the equilibrium solution under a deterministic policy restriction is fully revealing, quantized or noninformative, there exists a randomized sender policy that improves the sender's payoff under certain conditions characterized in the paper. Moreover, we provide an algorithmic procedure to obtain the Bayesian persuasion solution, where the algorithm compares the payoffs with finitely many posterior probability combinations. We also consider fully aligned and completely misaligned payoff structures, where the solutions respectively involve a fully revealing sender and a noninformative sender. Then, we unify these results by proving that if the sender's expected payoff with respect to posterior distributions is continuous, then the equilibrium solution involves either a fully revealing sender or a noninformative sender.

0.20

Social Learning of Ranking: Getting the Top Right despite Local Herding

cs.DS ·2026-10-11 ·Shahrzad Haddadan, Jie Gao
hot direction similarity 0.58
Abstract

In sequential learning, a group of agents sequentially receives a noisy private signal and observes the predictions of prior agents to estimate a hidden ground truth. While extensively studied for binary signals, we formalize and analyze sequential learning when the hidden ground truth is an ordering of $n$ items, and both private signals and inferences involve pairwise comparisons. A key focus in sequential learning is herding, where agents disregard their private signals to follow the crowd. We show that, while local herding in our model may lead agents to make incorrect pairwise inferences, the global hidden order can still be approximated. Specifically, by aggregating all pairwise comparison outputs, the highest-ranked items can be retrieved. We investigate top-$k$ retrieval across three scenarios: (1) passive aggregation, where information is gathered from the social learning process without intervention; (2) strategic selection, where agents choose their pairwise comparisons dynamically; and (3) aggregation with stubborn nodes, where a very small set of stubborn agents, who base their inferences solely on their private signals, join the mechanism. With query complexity as the number of agents needed for a high-probability estimation, we propose top-$k$ retrieval algorithms with query complexities sublinear in $O(n^2)$, the total number of pairs.

0.34

The Deceptive Bandit Problem: Exploratory Coupling and the Fragility of Multi-Agent Learning

cs.LG eess.SY ·2026-10-06 ·Michael Tang, Mahmoud Abdelgalil, Jorge I. Poveda
theoryhot direction similarity 0.58
Abstract

Randomized exploration is central to bandit learning, multi-agent reinforcement learning, and zeroth-order policy search, yet its independence and privacy are usually only treated as technical assumptions. We show that these properties are critical for security purposes and demonstrate how an adversarial agent can exploit privileged information on another agent's exploration. We analyze a deceiver-victim pair in the minimal two-player strongly monotone setting, where a deceptive player obtains leaked signals that are merely correlated with the victim's exploration. We show that, by coupling their own exploratory action with this information, the deceptive player injects an externality that steers the learning dynamics to a new steady state, called the deceptive Nash equilibrium (DNE). We prove that the deceptive bandit learning (DBL) dynamics converge to an arbitrarily small neighborhood of the DNE while retaining optimal convergence rates. Interestingly, our analysis attains these optimal rates while relaxing second-order smoothness conditions from standard bandit optimization literature. We characterize conditions under which deception strictly shifts the steady state and its effect on the deceiver's cost, illustrating the results in a resource-allocation game.

0.28

Information-Gain Calibrated On-Policy Distillation for Deep Search Agents

cs.IR ·2026-10-14 ·Chenxi Li, Xueyang Feng, Songyang Liu, Chenxu Wang, Xiaoying Tang +2 more
similarity 0.56
Abstract

On-policy distillation (OPD) has recently emerged as a promising approach for transferring the capabilities of large agents to compact students. In deep search, where agents iteratively retrieve external evidence, a teacher's preference among plausible queries before retrieval may not predict which queries will return useful evidence. Standard OPD nevertheless supervises each student query from the preceding context alone, inducing a failure mode we term \textbf{\textit{evidence-blind supervision (EBS)}}. To understand this, we regroup the OPD objective by interaction turns and reveal two implicit priors: a \textit{budget prior} that allocates supervision by token volume, and a \textit{direction prior} that favors tokens preferred by the teacher, neither of which accounts for the evidence returned by the current query. Our empirical analysis shows that both priors contribute to EBS in practice: the first search turn accounts for 51.1\% of total absolute information gain but receives only 18.0\% of the supervision budget, while 43.7\% of search queries have teacher rewards that disagree in sign with post-retrieval information utility. To mitigate this, we propose \ours, which uses post-retrieval information gain (IG) to calibrate both priors: reallocating supervision toward information-critical turns while calibrating query preferences using the utility of retrieved evidence. Experiments on six multimodal search benchmarks show that \ours improves average accuracy by 3.4 and 1.7 percentage points for 2B and 4B students over standard OPD, enabling the 4B student to surpass its 8B teacher on MMSearch and BrowseComp-VL.

0.21

Sample Complexity of Peer Prediction

cs.IT cs.GT ·2026-08-17 ·Abdellah Aznag, Robin Bowers, Rachel Cummings, Jason Hartline, Matthew vonAllmen +1 more
similarity 0.56
Abstract

Peer prediction seeks to incentivize agents to truthfully report an observed signal by rewarding joint sets of reports without observing a ground truth. Following the generalization of information-theoretic mutual information introduced in Kong and Schoenebeck (2019), we call a function of a joint distribution over signals a mutual information when it is non-negative and disincentivizes garbling reports for all information structures. An unbiased estimator for a mutual information takes some number of samples from the distribution and returns rewards for both agents, such that the expected reward is equal to the mutual information. We seek to characterize the set of mutual informations with unbiased estimators for a given number of samples. We show that for three or fewer sampled report pairs, the only mutual information with an unbiased estimator is trivially zero, and for four or five samples with a binary report space, the Determinant Mutual Information (DMI) of Kong (2024) is the unique mutual information (up to a scalar multiple). We further show that DMI ceases to be unique at six samples. We provide an improved estimator of DMI for any given number of samples and characterize its convergence rate. We also examine mutual information estimators that accept a randomized number of samples. First, we show that mutual information estimators on an ex-ante bounded number of samples (termed "stop-short estimators") can achieve a lower variance than an equivalent fixed-sample estimator (for DMI). Second, we introduce the class of scoring-rule-based mutual informations and identify in this family a mutual information that can be estimated with under three samples in expectation.

0.45

Contagious Misinterpretations: Social Learning with Shared Interpretations

cs.SI ·2026-10-14 ·Pol Rodríguez Farrés, Jesus Cerquides
similarity 0.56
Abstract

When people discuss which of several hypotheses is true, they share not only their beliefs but also their interpretation of each one, that is, the distribution of signals each hypothesis is expected to produce. This interpretation is an opinion about what each hypothesis means and what evidence it predicts, and it is revised only through conversation, not by confronting it with the observed data. Standard non-Bayesian social learning captures only belief-sharing and keeps the likelihoods private. We study what happens when agents share both beliefs and likelihoods under static networks. We show that interpretations converge geometrically to a common reading shaped by the most influential agents. Then, beliefs concentrate, almost surely and at an exponential rate, on the hypothesis that, under this consensus interpretation, best explains the signals privately observed by all agents taken together. As a result, sharing interpretations can lead a population to adopt, unanimously and confidently, a hypothesis it would have rejected if it had shared only beliefs. Whether this helps or hurts when a true hypothesis exists depends on how accurately agents initially read the data they observe. When every agent initially interprets the true hypothesis exactly as the data it would observe, sharing interpretations cannot strictly improve learning and can strictly harm it when agents observe different data distributions. When interpretations are logically coherent and some agents misread their own data, sharing can either rescue the population, leading it to learn the true hypothesis, if an accurate reading dominates the interpretation network, or corrupt it, leading it to a wrong hypothesis, if a misreading one does.

0.23

Partial Information Decomposition When Some Sources Are Known: A Source Chain Rule and a No-Go Theorem

cs.IT ·2026-10-24 ·Aaron J. Gutknecht
theory similarity 0.55
Abstract · 23 pages, 3 figures, 2 tables

Partial information decomposition (PID) splits the information that several sources carry about a target into atoms, distinguished by which collections of sources give access to them. We ask how such a decomposition should behave when some of the sources are already known. The access structure of the atoms suggests one answer: discard the atoms that the known sources provide and regroup the rest according to which further sources unlock them. The classical construction of conditional information suggests another: recompute the decomposition under the conditional distributions and average. We show that the two answers agree, atom by atom, exactly when redundant information obeys a source chain rule, an analogue of the chain rule of mutual information: when the same sources are added to several collections, the enlarged collections share everything the added sources provide and, beyond that, exactly what the original collections share once the added sources are known. The rule divides established measures of redundant information, so that adopting or rejecting it genuinely narrows the choice of measure. Our main result is a no-go theorem: for three or more sources, the source chain rule and local positivity, the requirement that all atoms be nonnegative, cannot hold together in any PID.

0.31

Wide Learning: Learning to Reach Evidence

cs.LG cs.AI ·2026-08-30 ·Junzhou Chen
similarity 0.55
Abstract

Machine learning is usually evaluated after an evidence interface has been fixed. A dataset, sensor suite, query language, action set, or experimental protocol determines which observations can be obtained, and learning is judged by what it extracts from them. We study a complementary capability. A learner's state can determine which evidence-generating experiments it can reliably realise under bounded resources, even when primitive affordances remain fixed. We call this learner-relative experiment family its effective epistemic reach, and use Wide Learning for task-relevant learning-induced changes in that family.We formalise effective reach relative to learner state, deployment budget, reliability threshold, and evaluation distribution. In a controlled construction, two hidden worlds have exactly the same public observation law. An informative diagnostic exists in a fixed five-primitive substrate. Before calibration, one address attempt realises it with probability at most $2^{-10} = 1/1024$, below a pre-specified 0.95 threshold; after calibration, held-out realisation is 1. Public-channel total variation is 0, whereas the realised diagnostic has total variation 1, and sealed binary risk moves from approximately 1/2 to 0. The construction establishes that learning can change effective epistemic reach even when primitive affordances and deployment resources are held fixed. It opens a complementary evaluation question for learning systems: not only what they infer from available evidence, but what informative evidence experience teaches them to bring within reach.

0.29