Learning Peer Influence Probabilities with Linear Contextual Bandits

Ahmed Sayeed Faruk; Elena Zheleva; Mohammad Shahverdikondori

REVIEW 4 major objections 5 minor 53 references

Learning Peer Influence Probabilities with Linear Contextual Bandits

T0 review · 4 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that learning peer influence probabilities in a networked bandit setting imposes a fundamental trade-off between minimizing cumulative regret and minimizing estimation error, characterizes all achievable trade-off rates, a

desk verdict The problem framing is genuinely new and the lower bound is sound, but Theorem 5.1 is not established by the written proof; the rate claims are probably right, but a real repair is needed. read the letter →

arxiv 2510.19119 v2 pith:5JJRQ3DX submitted 2025-10-21 cs.LG cs.SI

Ahmed Sayeed Faruk , Mohammad Shahverdikondori , Elena Zheleva This is my paper · ORCID

classification cs.LGcs.SI MSC 62L0562K0591D30

keywords peerinfluenceprobabilitylinearcontextualbanditsregretminimizationestimationerror(RMSE)Paretofrontierexploration-exploitationtrade-offcombinatorialsemi-banditssocialnetwork

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies an online learning problem where a platform picks k edges of a social network each round, shows one user's action to the other, and observes whether the recipient acts, thereby learning the influence probability of each edge from these interventions. It establishes a fundamental limit: no algorithm can simultaneously achieve the optimal rate of regret (reward lost by exploring) and the optimal rate of estimation error (how accurately influence probabilities are learned); any policy with a given regret rate must incur an estimation error at least as large as the reciprocal square root of that rate. The paper then proves a matching achievability result: a single algorithm, InfluenceCB, alternates between uncertainty-guided exploration and reward-guided exploitation, and by tuning one parameter attains every achievable regret/error rate pair. A sympathetic reader would care because influence probabilities drive viral marketing and diffusion research, and this result says any deployed system must explicitly choose which goal to sacrifice, while offering a dial for making that choice.

What carries the argument

The load-bearing object is the uncertainty measure U_t(X) = (X^T V_t^{-1} X)^{1/2} from linear bandit theory—the confidence-ellipsoid width for edge feature X—combined with a threshold rule that switches to exploration whenever the maximum uncertainty exceeds C/t^β; exploration then plays the k most uncertain edges, while otherwise the algorithm hands control to a regret-minimizing combinatorial linear bandit subroutine such as CombLinUCB. The lower bound rests on a two-group instance where the high-reward arms have mean 3/4 and the low-reward arms have mean 1/4, so that any play of a low-reward arm buys one Bernoulli sample of the second coordinate at a cost of 1/2 per play; a Bernoulli-mea

What would settle it

Run InfluenceCB on the exact two-group instance from the lower-bound proof—k arms with mean 0.75 and M−k arms with mean 0.25—with β = 1/4. The theory predicts regret Õ(T^(1/2)) and RMSE that cannot beat Ω(T^(−1/4)); any run that achieves regret Õ(T^(1/2)) with RMSE decaying faster than T^(−1/4) would falsify Theorem 4.2. Separately, a time-varying-pool experiment in which nature offers only a nearly collinear set S1 for T−1 rounds and reveals a distinct direction S2 on the final round would show RMSE on S2 failing to decay at all, pinpointing precisely where the theory stops.

Watch

Extended reading notes

Core claim

The central claim is that in the linear contextual bandit formulation of peer-influence learning, regret minimization and influence-probability estimation are in irreducible conflict. Theorem 4.2 constructs a linear bandit instance with k high-reward arms (mean 3/4) and M−k low-reward arms (mean 1/4) where any policy whose worst-case regret is O(T^(2β)) must suffer estimation error Ω(T^(−β)) on the low-reward arms, with β between 1/4 and 1/2. Consequently, achieving the optimal regret rate T^(1/2) forces the RMSE to be at least T^(−1/4), while achieving the optimal RMSE rate T^(−1/2) forces linear regret. Theorem 5.1 shows that the proposed InfluenceCB algorithm attains both bounds simultane

Load-bearing premise

The proofs assume the set of available edges is identical in every round; the paper itself states in Section 4 that once the pool varies (as it does in its own experiments, where edges are sampled fresh each round), no worst-case bound on estimation error can be guaranteed in general, so the practical RMSE guarantee rests on an assumption the evaluated setting does not satisfy.

Editorial extensions

If this is right

No contextual bandit can outperform the Pareto frontier: achieving Õ(T^(1/2)) regret necessarily leaves RMSE bounded below by Ω(T^(−1/4)), so the two optimal rates can never coexist.
A practitioner gets a principled dial: setting β near 1/4 targets low cumulative regret, setting β near 1/2 targets accurate influence estimates, and intermediate values interpolate predictably between the two extremes.
The exploration budget is provably controlled: the total number of exploration rounds is Õ(T^(2β)), so the final regret is dominated by the exploitation subroutine's own bound of Õ(k d √T).
The RMSE guarantee is uniform across edges: each arm's uncertainty shrinks to O(T^(−β)), so the per-edge prediction error for every influence probability, not just a selected subset, is bounded at the same rate.
The framework accepts any regret-minimizing combinatorial linear bandit as its exploitation engine, so the achievable-rate guarantee transfers to subroutines such as CombLinTS.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's theory is proven only for a fixed action pool (A_t = A every round), while its experiments use pools that change each round (500 random edges, or one random node's neighbors); a natural extension would be an exploration rule whose budget adapts to observed pool diversity, which could recover worst-case RMSE guarantees in the time-varying setting.
The trade-off argument is essentially an information-cost statement about low-reward arms, so the same rate frontier should persist under non-linear influence models; the paper's own non-linear misspecification experiments show regret trends survive while RMSE becomes erratic, which is consistent with that reading.
The β dial offers a way to set the exploration budget from business constraints: the value of one activation (regret) versus the value of knowing the network (RMSE) maps directly onto a choice of β, a parameterization none of the static or standard bandit baselines provide.
The trade-off implies a selection-bias warning for observational influence studies: any policy that greedily targets high-propensity edges will systematically underestimate the influence probabilities of weak ties—precisely the edges most relevant to seeding and diffusion analysis.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The thing to know about this paper: it's a good idea with a broken proof. The problem formulation — learning edge-level influence probabilities under k interventions per round, treating regret and RMSE as a bi-objective trade-off — is new, and the Pareto-frontier framing is a useful way to think about this problem. The lower bound (Theorem 4.2) is a standard information-theoretic construction and it's sound. The algorithm, InfluenceCB, is a sensible uncertainty-threshold design, and the experiments on two real networks with synthetic probabilities show the trade-off is real in practice. Also to the authors' credit, they explicitly flag that the theory assumes a fixed action set while the experiments use time-varying action pools.

Now the soft spots, and there are two real ones in Theorem 5.1's proof. First, inequality (5) derives ||X||_{V_t^{-1}} <= 1/sqrt(N_t(X)) from a Cauchy-Schwarz inequality that's written in the wrong direction. The claimed bound is actually true — you can get it from V_t >= NXX^T using the pseudo-inverse — so this specific error is repairable, but it has to be fixed. Second, and more serious: the uniform uncertainty bound ||X||_{V_T^{-1}} <= 2C/T^beta is asserted for arbitrary positive C, and that is false. Take two arms, k=1, beta=1/2, C=0.01: the algorithm explores every round and both arms keep uncertainty around sqrt(2/T), which is two orders of magnitude above 2C/sqrt(T). The proof's contradiction argument only excludes this when C^2 > 4M, a condition the theorem never states. The theorem's rate conclusions may still survive — in that example RMSE is Theta(T^{-1/2}), so the claimed rate holds — but the written proof does not deliver them. So the central achievability claim needs a genuine repair, probably a condition on C plus a case analysis.

Smaller issues: the regret combination with CombLinUCB is only sketched, the experiments come without error bars or code, and the conclusion's claim that the experiments 'corroborate the theoretical results' overreaches given the fixed-action-set gap. The adaptive C_t procedure in Algorithm 2 has many knobs (C_max, C_min, gamma, warmup, epsilon) and no analysis, which is fine for a heuristic but worth saying plainly.

This paper is for people working on influence learning and combinatorial bandits; the trade-off framing and the lower bound are worth engaging with. It deserves a serious referee — not a desk reject — but acceptance should wait for a corrected proof of Theorem 5.1 and a more honest experimental summary.

Referee Report

4 major / 5 minor

Summary. This paper studies the problem of learning edge-level peer influence probabilities as a bi-objective contextual linear bandit problem, where the two objectives are cumulative regret and the RMSE of the estimated influence probabilities. The main theoretical claims are: (i) Theorem 4.2, a worst-case lower bound showing that any policy with regret O(T^{2β}) must incur RMSE Ω(T^{-β}) for β in [1/4,1/2]; and (ii) Theorem 5.1, an achievability result for the proposed InfluenceCB algorithm, which alternates between uncertainty-threshold exploration and a regret-minimization subroutine, claiming to attain both rates simultaneously for any β in that interval. Experiments on two semi-synthetic network datasets compare InfluenceCB with static, online, and contextual-bandit baselines and show trade-offs controlled by β and C.

Significance. The bi-objective formulation and the proposed Pareto-frontier characterization are timely and potentially useful: if Theorem 5.1 were correctly established, the paper would provide a clean tunable interpolation between regret-optimal and estimation-optimal linear bandits, with clear practical relevance for influence-probability learning. The lower-bound idea is a standard information-theoretic construction, and the paper is honest about the fixed-action-set limitation of the theory. However, the central positive result is not established by the written proof: the proof of Theorem 5.1 contains a reversed matrix inequality and an unsupported uniform uncertainty bound, and the contradiction argument for the RMSE bound does not go through. The empirical study is broad and compares many baselines, but it operates in a time-varying action-pool regime that is explicitly outside the theorem's assumptions.

major comments (4)

[Appendix 8.3, Eq. (5)] The key inequality is stated in reverse. For positive definite A, Cauchy-Schwarz gives (u^T u)^2 ≤ (u^T A u)(u^T A^{-1}u), i.e., u^T A^{-1}u ≥ (u^T u)^2/(u^T A u), not ≤. The desired bound ∥X∥_{V_t^{-1}} ≤ 1/√N_t(X) may be true, but it requires a different proof, e.g., using V_t ⪰ λI + N_t(X)XX^T and Sherman-Morrison to obtain X^T V_t^{-1}X ≤ ∥X∥^2/(λ+N_t(X)∥X∥^2) ≤ 1/N_t(X). As written, the derivation of the exploration-count bound is invalid.
[Appendix 8.3, Eq. (9)] The uniform uncertainty bound ∥X∥_{V_T^{-1}} ≤ 2C/T^β is false for arbitrary positive C. For example, take M=2, k=1, A={e1,e2}, β=1/2, λ=1, C=0.01. The exploration condition is satisfied in every round, and under balanced exploration U_T(e1)≈√(2/T), while 2C/T^β = 0.02/√T, so (9) fails. Moreover, the contradiction step 'if U_T(X)>2C/T^β then X is the argmax in every t∈[T/2,T]' does not follow: high uncertainty for X does not imply that X is the chosen maximizer or is selected. The RMSE upper bound is therefore not established by the proof. The theorem statement needs either an explicit condition on C (e.g., C sufficiently large) or a corrected uniform bound with a constant depending on M and C.
[Sec. 4 vs. Sec. 6] The theoretical results are proved only under the fixed-action-set assumption A_t=A for all t, and the paper itself states in Section 4 that no uniform worst-case RMSE bound can be guaranteed when nature selects A_t. The experiments, however, use time-varying action pools: 500 randomly sampled edges per round in the network-based setting and a random node's neighbors in the neighbor-based setting. In addition, the main experiments use the adaptive C_t update from Algorithm 2, while Theorem 5.1 assumes a constant C_t=C. Thus the empirical evaluation does not cover the theoretical regime, and the practical claims about time-varying pools and adaptive thresholds are unsupported by the theory. Please either extend the analysis to these settings or explicitly frame the experiments as exploratory and outside the theorem's scope.
[Appendix 8.2, proof of Theorem 4.2] The lower-bound construction is underspecified. For low-reward arms of the form X_m=(0,1,x_{m,3},...,x_{m,d}), the prediction error is (θhat_{T,2}-1/4)+x_m^T θhat_{T,3:d}; the displayed inequality RMSE ≥ sqrt((M-k)/M) E|θhat_{T,2}-1/4| need not hold when the x_m terms are nonzero, since the contributions from coordinates 3,...,d can be present. If instead d=2 and all x_m are zero, the action list contains only two distinct feature vectors, so the 'M>k arms' claim relies on duplicate feature vectors; this should be stated explicitly. Please provide a complete instance and a rigorous reduction, or use a standard information-theoretic lower bound over a family of instances.

minor comments (5)

[Section 6.2.2] The estimated probability formula writes ê_{ij}.p = min(1, max(0, X^T θ^*)); this should use the estimate θhat_T, not the true parameter θ^*.
[Algorithm 1, line 4] The notation A_t∈A should be A_t⊆A (or 'A_t is a subset of A') to match the definition in Section 3.
[Algorithm 1 / Section 5.3] The subroutine f(F_t) is not formally defined: the input line says CMAB f(F_t), the pseudo-code calls f(F_{t-1}), and the text refers to the sampling policy at round t. Please define F_t and the subroutine interface consistently.
[Eq. (7)-(8), Appendix 8.3] The displayed regret bound 'Õ(c k d √T) + N/C² T^{2β}' is notationally unclear; the constant N (apparently from the exploration-count bound) should be made explicit and the sum written as O(T^{2β}) with the correct constant.
[Section 6.5] Experiments are repeated 10 times, but no error bars or standard deviations are reported in the figures/tables. Reporting variability would help assess the stability of the trade-off curves.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: lower bound is information-theoretic, upper bound is a design-rate proof; the only self-citation is background.

full rationale

The paper's central negative result (Theorem 4.2) constructs an explicit two-mean instance and invokes an external Bernoulli estimation lower bound (Lemma 8.1); the RMSE lower bound follows from the number of low-reward pulls implied by the regret budget, which is a standard information-theoretic argument, not an assumption of the conclusion. The central positive result (Theorem 5.1) analyzes InfluenceCB's exploration count and derives the claimed rates from the algorithm's own threshold rule and the external regret bound of CombLinUCB [41]; the rates are not obtained by fitting a parameter to the data being 'predicted' — β is a user-selected knob and C is a fixed constant in the theorem. The only self-citation is [12] (Faruk & Zheleva 2025), used in the related-work survey to note prior work that assumes known influence probabilities; it is not used in any proof and is not load-bearing. The paper explicitly limits its theoretical guarantees to fixed action sets (Section 4) and acknowledges that a uniform worst-case RMSE bound cannot be guaranteed under time-varying action pools, which is an honest limitation rather than a circular step. I did flag a separate correctness risk: the proof of Theorem 5.1 in Appendix 8.3 invokes a reversed Cauchy–Schwarz inequality (u^T A^{-1} u ≤ (u^T u)^2/(u^T A u)) and asserts the uniform uncertainty bound (9) for arbitrary positive C; these may invalidate the written proof. That concern is about mathematical validity, not circularity. Overall, the derivation chain does not reduce to its inputs by construction, and no load-bearing self-citation or fitted-input-called-prediction step is present.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The central lower-bound proof relies only on standard Bernoulli-mean estimation and the constructed two-direction arm set; the upper-bound proof relies on the ridge/self-normalized analysis of Abbasi-Yadkori et al. and the CombLinUCB regret bound of Wen et al. The load-bearing modeling axiom is linearity; the most restrictive auxiliary assumption is the constant action set A_t=A used in both main theorems.

free parameters (4)

β
User-tunable exploration parameter. The theorem's rate pair (Regret T^{2β}, RMSE T^{-β}) is parameterized by β; it is not fitted to data but is a hand-chosen knob that controls the trade-off.
C (threshold constant in theory)
Positive constant in the exploration threshold C/t^β. The proof of Theorem 5.1 requires C large enough for β=1/2. In experiments, C is fixed to values in {1,3,5,7,9} or adaptively learned, and the results depend on this choice.
λ (ridge regularization)
Regularization constant in V_t and in the ridge estimator. Standard in linear bandits, but needed for the self-normalized bound; its value influences the constants in the bounds.
Adaptive C_t hyperparameters (C_max, C_min, γ, warmup, ε)
Algorithm 2 (appendix) uses these to adaptively set the threshold in experiments. The theoretical theorem assumes fixed C, so these are experimental free parameters.

assumptions (6)

domain assumption Linear reward model: E[r] = X^T θ* for unknown θ*∈R^d
Section 3 states this linear model for expected reward. The entire theory and the experimental ground-truth generation (for the main setting) assume this. If influence probabilities are not linear in features, the guarantees do not hold in theory.
domain assumption Fixed action set for theory: A_t = A for all t
Section 4 explicitly restricts the theoretical analysis to a constant action set, acknowledging that for time-varying pools no worst-case RMSE bound can be guaranteed. Both Theorem 4.2 and Theorem 5.1 rely on this.
standard math Standard self-normalized bound for ridge estimator (Abbasi-Yadkori et al.)
Used in the proofs of Lemma 4.1 and Theorem 5.1 to translate parameter error into prediction error. Cited as [1].
standard math Regret lower bound for combinatorial semi-bandits (Audibert et al.)
Used to justify β ≥ 1/4 in Theorem 4.2. Cited as [5].
standard math Binary rewards are 1/2-sub-Gaussian
Used in the self-normalized bound of [1]. Standard for Bernoulli rewards.
standard math Arm set spans R^d and has bounded norms
Stated as standard assumptions in Section 3, needed for linear bandit analysis and for the G-optimal design construction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Learning Peer Influence Probabilities with Linear Contextual Bandits." pith.science (2026). https://pith.science/paper/5JJRQ3DX

@misc{pith2026251019119,
  author       = {Pith},
  title        = {Pith review of: Learning Peer Influence Probabilities with Linear Contextual Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5JJRQ3DX}},
  note         = {Machine review of arXiv:2510.19119}
}

read the original 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.

Figures

Figures reproduced from arXiv: 2510.19119 by the authors.

**Figure 1.** Trade-off between cumulative regret (𝑅𝑒𝑔𝑟𝑒𝑡𝑇 ) and estimation error (𝑅𝑀𝑆𝐸𝑇 ) in 𝐼𝑛 𝑓 𝑙𝑢𝑒𝑛𝑐𝑒𝐶𝐵(𝛽,𝐶) across linear network-based settings on the semi-synthetic datasets. The results illustrate how increasing 𝐶 shifts the trade-off: larger 𝐶 consistently reduces 𝑅𝑒𝑔𝑟𝑒𝑡𝑇 but leads to higher 𝑅𝑀𝑆𝐸𝑇 , with the trade-off depending on the choice of 𝛽. method when the function is misspecified. The third experiment evaluates 𝐼… view at source ↗

**Figure 2.** Tradeoff between 𝑅𝑒𝑔𝑟𝑒𝑡𝑇 (solid) and 𝑅𝑀𝑆𝐸𝑇 (dotted) for 𝐼𝑛 𝑓 𝑙𝑢𝑒𝑛𝑐𝑒𝐶𝐵 variants compared to 𝐿𝑖𝑛𝑈𝐶𝐵 for varying 𝑘. 7 Conclusion and Future Work This work introduced a novel formulation of learning heterogeneous peer influence probabilities in networked environments under a contextual linear bandit framework. We proved the existence of a fundamental trade-off between cumulative regret and estimation error, character… view at source ↗

**Figure 3.** Pareto frontiers of cumulative regret 𝑅𝑒𝑔𝑟𝑒𝑡𝑇 versus estimation error 𝑅𝑀𝑆𝐸𝑇 for InfluenceCB(𝛽, O) compared to baseline bandit and online models on semi-synthetic datasets. InfluenceCB expands the Pareto frontier and enables tunable trade-offs, with a notably smoother frontier on BlogCatalog. Varying 𝛽 and 𝐶 shifts the curve between low-regret and low-error regimes. Algorithm 2 UpdateC: Adaptive Computation of 𝐶𝑡 1: … view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Trade-off between cumulative regret (𝑅𝑒𝑔𝑟𝑒𝑡𝑇 ) and estimation error (𝑅𝑀𝑆𝐸𝑇 ) in 𝐼𝑛 𝑓 𝑙𝑢𝑒𝑛𝑐𝑒𝐶𝐵(𝛽,𝐶) under a nonlinear network-based setting. Peer influence probabilities are generated via a feed-forward neural network to simulate model misspecification. Results on Flic…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 4 linked inside Pith

[1]

Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. 2011. Improved algo- rithms for linear stochastic bandits. Advances in neural information processing systems 24 (2011)

2011
[2]

Abhineet Agarwal, Anish Agarwal, Lorenzo Masoero, and Justin Whitehouse
[3]

Aris Anagnostopoulos, Ravi Kumar, and Mohammad Mahdian. 2008. Influence and correlation in social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. 7–15

2008
[4]

Nicolás Aramayo, Mario Schiappacasse, and Marcel Goic. 2023. A multiarmed bandit approach for house ads recommendations. Marketing Science 42, 2 (2023), 271–292

2023
[5]

Jean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. 2014. Regret in online combinatorial optimization. Mathematics of Operations Research 39, 1 (2014), 31–45

2014
[6]

Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. 2022. EE- Net: Exploitation-Exploration Neural Networks in Contextual Bandits. In International Conference on Learning Representations

2022
[7]

Léon Bottou. 2010. Large-scale machine learning with stochastic gradient de- scent. In Proceedings of COMPSTAT’2010: 19th International Conference on Computational StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers. Springer, 177–186

2010
[8]

Nicolo Cesa-Bianchi and Gábor Lugosi. 2012. Combinatorial bandits. J. Comput. System Sci. 78, 5 (2012), 1404–1422

2012

Show all 53 references

[9]

Pritish Chakraborty, Sayan Ranu, Krishna Sri Ipsit Mantri, and Abir De. 2023. Learning and maximizing influence in social networks under capacity constraints. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining. 733–741

2023
[10]

Wei Chen, Yajun Wang, and Yang Yuan. 2013. Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning. PMLR, 151–159

2013
[11]

Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, et al. 2015. Combinatorial bandits revisited. Advances in neural information processing systems 28 (2015)

2015
[12]

Ahmed Sayeed Faruk and Elena Zheleva. 2025. Leveraging Heterogeneous Spillover in Maximizing Contextual Bandit Rewards. InProceedings of the ACM on Web Conference 2025 (Sydney NSW, Australia)(WWW ’25). Association for Computing Machinery, New York, NY, USA, 3049–3060. doi:10.1...

2025 doi
[13]

Jonathan Frenzen and Kent Nakamoto. 1993. Structure, cooperation, and the flow of market information. Journal of consumer research 20, 3 (1993), 360–375

1993
[14]

Chenbo Fu, Minghao Zhao, Lu Fan, Xinyi Chen, Jinyin Chen, Zhefu Wu, Yongxi- ang Xia, and Qi Xuan. 2018. Link weight prediction using supervised learning methods and its application to yelp layered network. IEEE Transactions on Knowledge and Data Engineering 30, 8 (2018), 1507–1518

2018
[15]

Chen Gao, Chao Huang, Donghan Yu, Haohao Fu, Tzh-Heng Lin, Depeng Jin, and Yong Li. 2022. Item recommendation for word-of-mouth scenario in social E- commerce. IEEE Transactions on Knowledge and Data Engineering 34, 6 (2022), 2798–2809

2022
[16]

Amit Goyal, Francesco Bonchi, and Laks VS Lakshmanan. 2010. Learning influence probabilities in social networks. In Proceedings of the third ACM international conference on Web search and data mining. 241–250

2010
[17]

Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. 2009. Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions. (2009)

2009
[18]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017)

2017
[19]

Linda D Hollebeek, Viktorija Kulikovskaja, Marco Hubert, and Klaus G Grunert
[20]

Alexandra Iacob, Bogdan Cautis, and Silviu Maniu. 2022. Contextual Ban- dits for Advertising Campaigns: A Diffusion-Model Independent Approach. In Proceedings of the 2022 SIAM International Conference on Data Mining (SDM). SIAM, 513–521

2022
[21]

Mohsen Jamali and Martin Ester. 2009. Using a trust network to improve top-n recommendation. In Proceedings of the third ACM conference on Recommender systems. 181–188

2009
[22]

Fateme Jamshidi, Mohammad Shahverdikondori, and Negar Kiyavash. 2025. Graph-dependent regret bounds in multi-armed bandits with interference. arXiv preprint arXiv:2503.07555 (2025)

2025
[23]

Su Jia, Peter Frazier, and Nathan Kallus. 2024. Multi-armed bandits with interfer- ence. arXiv preprint arXiv:2402.01845 (2024)

2024 arXiv
[24]

Maosheng Jiang, Yonxiang Chen, and Ling Chen. 2015. Link prediction in networks with nodes attributes by similarity propagation. arXiv preprint arXiv:1502.04380 (2015)

2015 arXiv
[25]

Lini Kuang, Ni Huang, Yili Hong, and Zhijun Yan. 2019. Spillover effects of finan- cial incentives on non-incentivized user engagement: Evidence from an online knowledge exchange platform. Journal of Management Information Systems 36, 1 (2019), 289–320

2019
[26]

Ajay Kumar, Shashank Sheshar Singh, Kuldeep Singh, and Bhaskar Biswas. 2020. Link prediction techniques, applications, and performance: A survey. Physica A: Statistical Mechanics and its Applications 553 (2020), 124289

2020
[27]

Konstantin Kutzkov, Albert Bifet, Francesco Bonchi, and Aristides Gionis. 2013. Strip: stream learning of influence probabilities. InProceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 275–283

2013
[28]

Tor Lattimore and Csaba Szepesvári. 2020. Bandit algorithms. Cambridge Uni- versity Press

2020
[29]

Lihong Li, Wei Chu, John Langford, and Robert E Schapire. 2010. A contextual- bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web. 661–670

2010
[30]

Haohui Lu and Shahadat Uddin. 2024. A parameterised model for link predic- tion using node centrality and similarity measure based on graph embedding. Neurocomputing 593 (2024), 127820

2024
[31]

Cameron Marlow, Mor Naaman, Danah Boyd, and Marc Davis. 2006. HT06, tagging paper, taxonomy, Flickr, academic article, to read. InProceedings of the seventeenth conference on Hypertext and hypermedia. 31–40

2006
[32]

Mark EJ Newman. 2003. Mixing patterns in networks. Physical review E 67, 2 (2003), 026126

2003
[33]

Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al . 2011. Scikit-learn: Machine learning in Python. the Journal of machine Learning research 12 (2011), ...

2011
[34]

Kazumi Saito, Ryohei Nakano, and Masahiro Kimura. 2008. Prediction of infor- mation diffusion probabilities for independent cascade model. In International conference on knowledge-based and intelligent information and engineering systems. Springer, 67–75

2008
[35]

Shai Shalev-Shwartz et al. 2012. Online learning and online convex optimization. Foundations and Trends® in Machine Learning 4, 2 (2012), 107–194

2012
[36]

Cosma Rohilla Shalizi and Andrew C Thomas. 2011. Homophily and contagion are generically confounded in observational social network studies. Sociological methods & research 40, 2 (2011), 211–239

2011
[37]

Dongjin Song, David A Meyer, and Dacheng Tao. 2015. Top-k link recommenda- tion in social networks. In 2015 IEEE International Conference on Data Mining. IEEE, 389–398

2015
[38]

Karthik Subbian, Charu C Aggarwal, and Jaideep Srivastava. 2016. Querying and tracking influencers in social streams. In Proceedings of the ninth ACM international conference on Web search and data mining. 493–502

2016
[39]

Sharan Vaswani, Branislav Kveton, Zheng Wen, Mohammad Ghavamzadeh, Laks VS Lakshmanan, and Mark Schmidt. 2017. Model-independent online learning for influence maximization. In International Conference on Machine Learning. PMLR, 3530–3539

2017
[40]

Xiyuan Wang, Haotong Yang, and Muhan Zhang. 2024. Neural Common Neighbor with Completion for Link Prediction. In The Twelfth International Conference on Learning Representations

2024
[41]

Zheng Wen, Branislav Kveton, and Azin Ashkan. 2015. Efficient learning in large-scale combinatorial semi-bandits. In International Conference on Machine Learning. PMLR, 1113–1122

2015
[42]

Zheng Wen, Branislav Kveton, Michal Valko, and Sharan Vaswani. 2017. Online influence maximization under independent cascade model with semi-bandit feedback. Advances in neural information processing systems 30 (2017)

2017
[43]

Bryan Wilder, Nicole Immorlica, Eric Rice, and Milind Tambe. 2018. Maximizing influence in an unknown social network. InProceedings of the AAAI Conference on Artificial Intelligence, Vol. 32

2018
[44]

Yang Xu, Wenbin Lu, and Rui Song. 2024. Linear contextual bandits with inter- ference. arXiv preprint arXiv:2409.15682 (2024)

2024 arXiv
[45]

Yukuan Xu, Juan Luis Nicolau, and Peng Luo. 2022. Travelers’ reactions toward recommendations from neighboring rooms: Spillover effect on room bookings. Tourism Management 88 (2022), 104427

2022
[46]

Xiwang Yang, Harald Steck, Yang Guo, and Yong Liu. 2012. On top-k recommen- dation using social networks. In Proceedings of the sixth ACM conference on Recommender systems. 67–74

2012
[47]

Jing Zhang, Jie Tang, Yuanyi Zhong, Yuchen Mo, Juanzi Li, Guojie Song, Wendy Hall, and Jimeng Sun. 2017. Structinf: Mining structural influence from so- cial streams. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 31

2017
[48]

Zhiheng Zhang and Zichen Wang. 2024. Online experimental design with estimation-regret trade-off under network interference. arXiv preprint arXiv:2412.03727 (2024)

2024 arXiv
[49]

Zizhu Zhang, Weiliang Zhao, Jian Yang, Cecile Paris, and Surya Nepal. 2019. Learning influence probabilities and modelling influence diffusion in twitter. In Companion Proceedings of The 2019 World Wide Web Conference. 1087–1094. Ahmed Sayeed Faruk, Mohammad Shahverdikondori, ...

2019
[52]

Let the action set be A0 ={𝑋 1,...,𝑋 𝑀}, 𝑋 𝑚 = ( (1,0,𝑥 𝑚,3,...,𝑥 𝑚,𝑑),1≤𝑚≤𝑘, (0,1,𝑥 𝑚,3,...,𝑥 𝑚,𝑑), 𝑘<𝑚≤𝑀, and set the true parameter vector to 𝜃∗ 0 = 3 4, 1 4,0,...,0

as follows. Let the action set be A0 ={𝑋 1,...,𝑋 𝑀}, 𝑋 𝑚 = ( (1,0,𝑥 𝑚,3,...,𝑥 𝑚,𝑑),1≤𝑚≤𝑘, (0,1,𝑥 𝑚,3,...,𝑥 𝑚,𝑑), 𝑘<𝑚≤𝑀, and set the true parameter vector to 𝜃∗ 0 = 3 4, 1 4,0,...,0 . The expected reward of arm 𝑚 is𝑋⊤ 𝑚𝜃∗ 0, so the first 𝑘 arms are high-reward arms with mean3/4...
[53]

This completes the proof.□ 8.3 Proof of Theorem 5.1 Proof

≥𝐶′ √︄ 𝑀−𝑘 𝑀𝑘𝑇(1−𝛼) ∈Ω(𝑇 −𝛽), where constants depending on𝑘 are absorbed into the asymptotic notation. This completes the proof.□ 8.3 Proof of Theorem 5.1 Proof. Let the set of available actions be fixed as A for all rounds, and let∀𝑡 : 𝐶𝑡 =𝐶 . For each round 𝑡 and arm 𝑋∈A , d...
[2023]

Internet Research 33, 4 (2023), 1573–1596

Exploring a customer engagement spillover effect on social media: the moderating role of customer conscientiousness. Internet Research 33, 4 (2023), 1573–1596

2023
[2024]

Advances in Neural Information Processing Systems 37 (2024), 36414–36437

Mutli-Armed Bandits with Network Interference. Advances in Neural Information Processing Systems 37 (2024), 36414–36437

2024

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. 2011. Improved algo- rithms for linear stochastic bandits. Advances in neural information processing systems 24 (2011)

2011

[2] [2]

Abhineet Agarwal, Anish Agarwal, Lorenzo Masoero, and Justin Whitehouse

[3] [3]

Aris Anagnostopoulos, Ravi Kumar, and Mohammad Mahdian. 2008. Influence and correlation in social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. 7–15

2008

[4] [4]

Nicolás Aramayo, Mario Schiappacasse, and Marcel Goic. 2023. A multiarmed bandit approach for house ads recommendations. Marketing Science 42, 2 (2023), 271–292

2023

[5] [5]

Jean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. 2014. Regret in online combinatorial optimization. Mathematics of Operations Research 39, 1 (2014), 31–45

2014

[6] [6]

Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. 2022. EE- Net: Exploitation-Exploration Neural Networks in Contextual Bandits. In International Conference on Learning Representations

2022

[7] [7]

Léon Bottou. 2010. Large-scale machine learning with stochastic gradient de- scent. In Proceedings of COMPSTAT’2010: 19th International Conference on Computational StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers. Springer, 177–186

2010

[8] [8]

Nicolo Cesa-Bianchi and Gábor Lugosi. 2012. Combinatorial bandits. J. Comput. System Sci. 78, 5 (2012), 1404–1422

2012