Technical Summary: Learning Peer Influence Probabilities with Linear Contextual Bandits

1. Problem Formulation

The paper addresses the challenge of learning heterogeneous peer influence probabilities in networked environments. In social networks, the probability that a user (recipient) adopts an action after receiving a recommendation from another user (sender) varies significantly based on node attributes, edge characteristics, and network structure.

The authors formulate this as a bi-objective contextual multi-armed bandit (CMAB) problem. The setting involves an agent interacting with a directed attributed network $G=(V, E)$ over $T$ rounds. In each round:

1. The agent observes a pool of candidate edges (interactions).
2. The agent selects a subset of $k$ edges for intervention (e.g., showing a post to a specific set of recipients).
3. The agent observes binary rewards (activation: 1 if the recipient acts, 0 otherwise).

The core difficulty lies in balancing two conflicting objectives:

• Minimizing Cumulative Regret ($Regret_T$): Maximizing immediate rewards by selecting edges with the highest estimated influence probabilities (exploitation).
• Minimizing Estimation Error ($RMSE_T$): Accurately estimating the true influence probabilities for all edges in the network, including those with low or uncertain influence (exploration).

The paper argues that standard online learning methods either waste resources via random exploration (low regret guarantees) or optimize solely for rewards, leading to high estimation errors for low-probability edges. Conversely, static methods fail to disentangle true influence from confounding factors like homophily.

2. Methodology: Influence Contextual Bandit ($InfluenceCB$)

The authors propose $InfluenceCB$, a framework designed to navigate the trade-off between regret and estimation error. The method operates under a linear reward model where the expected reward for an edge with context vector $X$ is $E[r] = X^\top \theta^*$, with $\theta^*$ being an unknown parameter vector.

Key Components:

1. Uncertainty-Guided Exploration:

   • The algorithm computes the estimation uncertainty for candidate edges using the standard linear bandit uncertainty metric: $U_t(X) = \sqrt{X^\top V_{t-1}^{-1} X}$, where $V_{t-1}$ is the regularized covariance matrix of observed features.
   • If the maximum uncertainty in the current pool exceeds a dynamic threshold ($C_t / t^\beta$), the algorithm enters an exploration phase, selecting the top-$k$ edges with the highest uncertainty scores. This ensures that low-probability or uncertain edges are sampled to improve global estimation.

2. Reward-Guided Exploitation:

   • If uncertainty falls below the threshold, the algorithm enters an exploitation phase.
   • It employs a standard linear CMAB subroutine (e.g., CombLinUCB) to select edges that maximize expected immediate rewards, thereby minimizing regret.

3. Trade-off Control:

   • Parameter $\beta$: Controls the asymptotic rate of the trade-off. A lower $\beta$ (e.g., 0.25) prioritizes regret minimization, while a higher $\beta$ (e.g., 0.5) prioritizes estimation accuracy (RMSE).
   • Parameter $C_t$: An adaptive threshold learned over time based on activation rates or uncertainty statistics, allowing the system to adjust the balance between exploration and exploitation dynamically.

3. Theoretical Contributions

The paper provides rigorous theoretical analysis establishing the fundamental limits of this problem:

• Existence of a Trade-off: The authors prove that no single algorithm can simultaneously achieve the optimal rates for both cumulative regret and global estimation error.
• Achievable Rate Pairs: They characterize the Pareto frontier of achievable rates. Specifically, for any policy $\pi$, if the regret scales as $O(T^{2\beta})$, the RMSE must scale as $\Omega(T^{-\beta})$, where $\beta \in [1/4, 1/2]$.
  • Optimal regret ($\beta=1/4$) implies sub-optimal RMSE ($\Omega(T^{-1/4})$).
  • Optimal RMSE ($\beta=1/2$) implies linear regret.
• Achievability: Theorem 5.1 demonstrates that $InfluenceCB$ can attain any point on this Pareto frontier by tuning the parameter $\beta$, satisfying the bounds:
  $$Regret_T \in \tilde{O}(T^{2\beta}), \quad RMSE_T \in \tilde{O}(T^{-\beta})$$

4. Experimental Results

The authors evaluated $InfluenceCB$ on three semi-synthetic datasets derived from real-world networks: BlogCatalog, Flickr, and Hateful (Twitter). Ground-truth influence probabilities were generated synthetically based on linear combinations of node and edge features.

Baselines:

• Static Models: Random, Similarity, Link Prediction (Ridge, GraphSAGE, NCNC), and a SOTA Recommender (ContextGNN).
• Online Learning: SGD-based exploitation and exploration variants.
• Contextual Bandits: LinUCB, EENet, Graph Neural Bandits (GNB), and Takemura et al. (combinatorial semi-bandit).

Key Findings:

• Pareto Frontier Expansion: $InfluenceCB$ expands the Pareto frontier beyond all baselines. While standard bandits (like LinUCB) optimize for regret, they exhibit higher estimation errors. Static models perform poorly on both metrics.
• Tunable Trade-offs: By adjusting $\beta$, $InfluenceCB$ can significantly reduce RMSE (up to ~60% on Flickr) at the cost of increased regret, or minimize regret (outperforming LinUCB by ~5-10%) with a slight increase in RMSE.
• Parameter Sensitivity: The parameter $C$ (threshold) significantly impacts the trade-off. The adaptive learning of $C$ allows the algorithm to find a balance without manual tuning for specific application needs.
• Robustness: The method maintains competitive performance in ranking metrics (NDCG@k) and calibration error (ECE) across different network settings (network-based vs. neighbor-based edge selection).

5. Significance and Claims

The paper claims to be the first to explicitly formulate learning peer influence probabilities as an independent bi-objective problem, distinct from influence maximization or recommendation tasks where probabilities are assumed known or secondary.

• Theoretical Insight: It establishes that minimizing regret and minimizing global estimation error are fundamentally conflicting objectives in networked bandit settings, a trade-off previously uncharacterized in this specific context.
• Practical Utility: The framework allows practitioners to explicitly choose a policy aligned with their application's priorities. For instance, a viral marketing campaign might prioritize regret (immediate sales), while a policy audit or diffusion simulation might prioritize RMSE (accurate global influence maps).
• Limitations and Future Work: The authors note that their current analysis assumes independent Bernoulli activations and does not model complex interference effects (e.g., cumulative exposure from multiple neighbors). Future work is suggested to extend the framework to non-linear settings and dynamic or partially observed networks.

In summary, $InfluenceCB$ provides a principled mechanism to navigate the tension between learning accurate influence models and maximizing immediate network interventions, offering a flexible tool for networked decision-making.