Learning Peer Influence Probabilities with Linear Contextual Bandits

AI summary

Overview

Research area: Online learning and social network analysis — specifically, using linear contextual bandits to estimate peer influence probabilities in attributed networks, bridging influence estimation with sequential decision-making theory.

Technical level: Intermediate to Advanced. The paper is accessible to readers familiar with multi-armed bandits and linear models, but its central results are worst-case rate analyses (regret and RMSE bounds), Pareto-frontier characterization, and a bi-objective algorithm design that assumes comfort with asymptotic notation.

One-sentence scope: The paper formalizes peer influence probability learning as a bi-objective combinatorial linear contextual bandit, proves a fundamental trade-off between minimizing cumulative regret and minimizing global estimation error, and proposes an uncertainty-guided algorithm (InfluenceCB) that can be tuned to attain any achievable point on that trade-off curve.

What This Paper Is About

In social and e-commerce platforms, one user's action (sharing a post, recommending a product) may or may not lead another user to act. The probability of that adoption — the peer influence probability — is heterogeneous and context-dependent, and correctly estimating it matters for understanding information diffusion and for viral marketing. The problem is that observational data only shows correlations (confounded by homophily, confounding factors, and coincidence), while online learning algorithms that intervene either waste resources on random exploration or chase high-reward edges and therefore never learn the full range of influence probabilities.

This paper asks: can an agent that intervenes on only k edges per round simultaneously act well (minimize regret) and learn influence probabilities accurately across all edges (minimize root mean squared error, RMSE)? The authors show the two goals fundamentally conflict, characterize exactly which pairs of rates are achievable, and provide an algorithm that lets a practitioner dial in the desired trade-off with a single parameter.

Key Contributions

1. Bi-objective problem formulation. The authors cast learning heterogeneous peer influence probabilities in networks as a bi-objective contextual multi-armed bandit, where each round the agent observes a pool of candidate directed edges, selects k edges for intervention, observes binary adoption outcomes, and is evaluated on both cumulative regret and global RMSE over all edges.

2. A fundamental trade-off theorem. They prove that for any M > k there exists an instance where any policy with regret in O(T^{2β}) must have RMSE in Ω(T^{-β}), with β ≤ 1/2 and 1/4 ≤ β enforced by the regret lower bound, and they characterize all achievable rate pairs.

3. The InfluenceCB framework. They propose an Influence Contextual Bandit framework that alternates between uncertainty-guided exploration (selecting the top-k highest-uncertainty edges) and reward-guided exploitation (delegating to an input linear CMAB such as CombLinUCB or CombLinTS), with a dynamic threshold C_t / t^β deciding which phase is used each round.

4. Tunable position on the Pareto frontier. They show theoretically that by tuning the single exploration parameter β, InfluenceCB attains any feasible rate pair implied by the trade-off theorem — for example, β = 1/4 optimizes regret while β = 1/2 optimizes RMSE.

Main Findings

• The two objectives are in direct conflict. Minimizing regret concentrates exploration on high-reward edges, leaving large regions of the influence-probability space underexplored; minimizing estimation error requires exploring uncertain or low-reward edges, which raises regret. No single policy can minimize both.

• Optimal individual rates are T^{1/2} for regret and T^{-1/2} for RMSE. The paper reports that the combinatorial linear bandit problem with semi-bandit feedback has a CombLinUCB worst-case regret upper bound of Õ(kd√T) and a lower bound of Ω(d√kT) from prior work (Takemura et al., 2021); these bounds are described as close but not matching.

• A new RMSE upper bound under a constrained design. Because the classical G-optimal design can assign some arms more than 1/k of the budget — infeasible when k distinct arms must be chosen per round — the authors define a constrained design f*(A, k) over the simplex with entries bounded by 1/k. Lemma 4.1 gives RMSE in Õ(√(f*(A, k) / (kT))). In the special case where the unconstrained optimum already lies in the constrained simplex and the action vectors span R^d, f*(A, k) = d; otherwise f*(A, k) is larger.

• Extreme choices of β give extreme outcomes. Setting β = 1/4 yields the optimal regret rate R_T = O(T^{1/2}) but forces RMSE to the non-optimal Ω(T^{-1/4}). Setting β = 1/2 yields the optimal RMSE rate Θ(T^{-1/2}) but forces cumulative regret to be linear.

• Entropy-style tuning of the threshold. The parameter C is learned online rather than fixed: Algorithm 2 updates it using a normalized deviation z between a history baseline and current statistics (activation rate for the regret objective, average uncertainty for RMSE), mapped through a sigmoid C_new = C_min + (C_max − C_min)/(1 + e^{−γz}), with the regret variant updating monotonically via C_t = max(C_prev, C_new).

• Guarantees hold under a fixed-action assumption. The theoretical results assume the available action set is constant across rounds (A_t = A). The authors explain that without this, a worst-case RMSE bound is impossible in general — for example, if actions split into a nearly collinear set S_1 and a distant set S_2, and nature repeatedly serves pools from S_1, the parameter is poorly estimated in the directions of S_2 and RMSE stays high. The algorithm itself and the experiments operate in the more general setting.

• The trade-off analysis is in T only. Remark 4.3 states explicitly that the analysis does not characterize dependence on other structural parameters such as d and k.

• Empirical results on semi-synthetic networks. The paper reports experiments on semi-synthetic network datasets showing advantages over static methods and over contextual bandits that ignore the trade-off. The specific datasets, dataset sizes, and numeric metrics are not reported in the available content (the experiments section is in the truncated portion).

• Computational cost scales with the action pool, not the graph. Complexity is governed primarily by the size of A_t, with uncertainty computations scaling as O(|A_t| d²) (the sentence continues into truncated text).

Methodology in Plain English

The authors model a platform that each round sees a pool of candidate peer-to-peer exposures (for instance, a post from one user shown to some of their neighbors), picks k of them, and observes whether each recipient took the action. Adoption is modeled as a linear function of an unknown parameter vector θ* applied to edge context features, so the estimated influence probability is just the probability of a positive reward.

They then treat this as a combinatorial linear bandit with semi-bandit feedback and go after two worst-case metrics at once: cumulative regret (how much reward is lost relative to always picking the true top-k edges) and global RMSE over every edge in the network, including rarely activated ones. The choice of global RMSE is deliberate — it keeps the problem from collapsing into ordinary regret minimization and preserves the tension.

To see how bad the tension is, they first bound each objective separately using known bandit results and a modified optimal-design argument. Then they construct a family of instances showing that pushing regret toward its optimal T^{1/2} rate necessarily pushes RMSE to Ω(T^{-1/4}) and vice versa, and they express the recoverable region of the trade-off with a single exponent β.

The proposed algorithm, InfluenceCB, operationalizes this. Each round it computes an uncertainty score U_t(X) = sqrt(X^T V_{t-1}^{-1} X) for every candidate edge and compares the maximum such score u_t against an adaptive threshold C_t / t^β. If uncertainty is high, it explores by intervening on the k most uncertain edges — cheap in regret terms but exactly what reduces estimation error. If uncertainty is low, it hands control to a standard regret-minimizing CMAB (CombLinUCB, CombLinTS, or any algorithm with comparable bounds). Over time, this keeps every edge's uncertainty on the order of O(T^{-β}), which is what produces the RMSE guarantee. A separate routine adjusts C_t from recent batch statistics so the threshold adapts rather than staying fixed. The combinatorial step is noted to be trivially solvable because the objective is additive, so the oracle just picks the k largest scores.

Why This Matters

Impact on research. The paper reframes influence probability learning as an estimation problem in its own right rather than a byproduct of reward maximization, and it supplies the first (per the authors) characterization of a regret–estimation Pareto frontier in networked bandit settings where only a small subset of edges is intervened on per round. It also gives downstream diffusion and influence-maximization research a principled way to obtain edge-level probabilities that observational methods cannot disentangle from homophily and confounding.

Real-world applications.

• Viral marketing and campaign targeting: choosing which peer recommendations to promote while still building a reliable model of who influences whom.
• Recommender and content platforms: deciding which recipient should be shown a friend's post or product share when adoption is uncertain.
• Diffusion simulation and counterfactual analysis: using globally accurate influence probabilities to simulate cascades under alternative seed sets, evaluate new policies offline without re-exploration, or audit influence patterns across user subgroups.
• Referral and growth programs: allocating a limited number of exposure "slots" per round across a large candidate edge pool.

Industry relevance. The setting maps directly onto the operational constraints of social and e-commerce platforms: interventions are limited (k per round), outcomes are binary and noisy, features are drawn from publicly visible or non-privacy-sensitive signals such as node, edge, item, and structural attributes, and the organization cares about both immediate engagement and an accurate long-run model of influence. The tunable β parameter gives practitioners an explicit control for choosing where to sit between short-term performance and model fidelity — and the authors provide source code publicly at https://doi.org/10.5281/zenodo.20500085.

Future Directions

• Extending guarantees beyond the fixed action pool. The theory assumes A_t = A for all t, and the authors show that a general worst-case RMSE bound is impossible when nature can restrict the pool. Characterizing what is achievable under natural assumptions on how pools are generated is left open.

• Characterizing dependence on d and k. Remark 4.3 states the trade-off analysis deliberately focuses on the exponent of T and does not specify dependence on the other structural parameters, leaving room for tighter, structurally explicit bounds.

• Tightening the regret bounds. The paper notes that the CombLinUCB upper bound and the Ω(d√kT) lower bound do not match, and that recent combinatorial CMAB work has produced tighter bounds under additional structural assumptions that were not adopted here.

• Connecting learned probabilities to diffusion and maximization. The authors note they do not model cascades or multi-hop diffusion, but suggest the learned edge probabilities could feed into diffusion simulation and influence maximization — and they observe that no existing work addresses recommending the top-k neighbors for sharing a fixed item, a gap their setting sits close to.

Target Audience

This paper is best suited to researchers and graduate students in machine learning, online learning, and computational social science who work on bandits, information diffusion, social network analysis, or recommender systems. It will also be useful to applied scientists and engineers at social, content, or e-commerce platforms who design peer-exposure or referral experiments and need to justify exploration budgets to stakeholders. Readers without a background in bandit theory can follow the problem motivation, the algorithm description, and the trade-off intuition, but the theorems and rate characterizations require familiarity with asymptotic notation and linear bandit analysis.

Authors’ abstract

In networked environments, it is common for users to share recommendations about content, products, services, and possible courses of action. Whether these recommendations are accepted and acted upon is highly context-dependent, influenced by the characteristics of the sender and recipient, the nature of their relationship, the attributes of the recommended item, and the communication context. Consequently, probabilities of peer influence exhibit substantial heterogeneity across individuals and settings. Accurate estimation of these probabilities is key to understanding information diffusion processes and to improving the effectiveness of viral marketing strategies. However, learning these probabilities from data is challenging; static data may capture correlations between peer recommendations and peer actions but fails to reveal influence relationships. Online learning algorithms can learn these probabilities from interventions but either waste resources by learning from random exploration or optimize for rewards, thus favoring exploration of the space with higher influence probabilities. In this work, we study learning peer influence probabilities under a contextual linear bandit framework. We show that a fundamental trade-off can arise between regret minimization and estimation error, characterize all achievable rate pairs, and propose an uncertainty-guided exploration algorithm that, by tuning a parameter, attains any pair within this trade-off. Our experiments on semi-synthetic network datasets show the advantages of our method over static methods and contextual bandits that ignore this trade-off.