{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,14]],"date-time":"2026-08-14T09:30:20Z","timestamp":1786699820941,"version":"build-2736575974"},"reference-count":42,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,8]]},"abstract":"<jats:p>We propose the analysis of the online learning problem for independent cascade (IC) models under node-level feedback. These models have widespread applications in modern social networks. Existing works for IC models have only shed light on edge-level feedback models, where the agent knows the explicit outcome of every observed edge. Little is known about node-level feedback models where only combined outcomes for sets of edges are observed; in other words, the realization of each edge is censored. This censored information, together with the nonlinear form of the aggregated influence probability, makes both parameter estimation and algorithm design challenging. We establish a confidence-region result under this setting. We develop an online algorithm achieving a cumulative regret of [Formula: see text], matching the theoretical regret bound for IC models with edge-level feedback. We also establish a framework to implement the offline oracle and provide its theoretical performance guarantee. Numerical experiments demonstrate the practical efficiency of our algorithm.<\/jats:p>\n                  <jats:p>Supplemental Material: The online appendix is available at https:\/\/doi.org\/10.1287\/moor.2021.0117 .<\/jats:p>","DOI":"10.1287\/moor.2021.0117","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T13:14:36Z","timestamp":1749820476000},"page":"1713-1732","source":"Crossref","is-referenced-by-count":0,"title":["Online Learning of Independent Cascade Models with Node-Level Feedback"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0915-196X","authenticated-orcid":false,"given":"Shuoguang","family":"Yang","sequence":"first","affiliation":[{"name":"Department of Industrial Engineering and Decision Analytics, The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Van-Anh","family":"Truong","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"109","reference":[{"key":"B1","unstructured":"Abbasi-Yadkori Y, P\u00e1l D, Szepesv\u00e1ri C (2011) Improved algorithms for linear stochastic bandits. Shawe-Taylor J, Zemel RS, Bartlett PL, Pereira F, Weinberger KQ, eds.\n                      NIPS\u201911: Proc. 25th Internat. Conf. Adv. Neural Inform. Processing Systems\n                      (Curran Associates Inc. Red Hook, NY), 2312\u20132320."},{"key":"B2","unstructured":"Agrawal S, Avadhanula V, Goyal V, Zeevi A (2017) Thompson sampling for the MNL-bandit.\n                      Conf. Learning Theory\n                      (PMLR, New York), 76\u201378."},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1832"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0598"},{"key":"B5","doi-asserted-by":"crossref","unstructured":"Bharathi S, Kempe D, Salek M (2007) Competitive influence maximization in social networks. Deng X, Graham FC, eds.\n                      Internet Network Econom. WINE 2007\n                      , Lecture Notes in Computer Science, vol. 4858 (Springer, Berlin, Heidelberg), 306\u2013311.","DOI":"10.1007\/978-3-540-77105-0_31"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1214\/08-AOS620"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1017938919"},{"key":"B8","unstructured":"Chen N, Li A, Yang S (2020) Revenue maximization and learning in products ranking. Preprint, submitted December 7, https:\/\/arxiv.org\/abs\/2012.03800."},{"key":"B9","unstructured":"Chen W, Wang Y, Yuan Y (2013) Combinatorial multi-armed bandit: General framework and applications.\n                      ICML\u201913: Proc. 30th Internat. Conf. Machine Learn.\n                      , vol. 28 (PMLR, New York), 151\u2013159."},{"issue":"1","key":"B10","first-page":"1746","volume":"17","author":"Chen W","year":"2016","journal-title":"J. Machine Learn. Res."},{"key":"B11","doi-asserted-by":"crossref","unstructured":"Chen W, Lin T, Tan Z, Zhao M, Zhou X (2016) Robust influence maximization.\n                      KDD\u201916: Proc. 22nd ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining\n                      (Association for Computing Machinery, New York), 795\u2013804.","DOI":"10.1145\/2939672.2939745"},{"key":"B12","unstructured":"Cheung WC, Tan V, Zhong Z (2019) A Thompson sampling algorithm for cascading bandits.\n                      22nd Internat. Conf. Artificial Intelligence Statist.\n                      (PMLR, New York), 438\u2013447."},{"key":"B13","unstructured":"Combes R, Talebi MS, Proutiere A, Lelarge M (2015) Combinatorial bandits revisited. Cortes C, Lee DD, Sugiyama M, Garnett R, eds.\n                      NIPS\u201915: Proc. 29th Internat. Conf. Adv. Neural Inform. Processing Systems\n                      , vol. 2 (MIT Press, Cambridge, MA), 2116\u20132124."},{"issue":"1","key":"B14","first-page":"39","volume":"12","author":"Fisher RA","year":"1997","journal-title":"Statist. Sci."},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2181864"},{"key":"B16","doi-asserted-by":"crossref","unstructured":"Goyal A, Bonchi F, Lakshmanan LVS (2010) Learning influence probabilities in social networks.\n                      WSDM \u201810: Proc. 3rd ACM Internat. Conf. Web Search Data Mining\n                      (Association for Computing Machinery, New York), 241\u2013250.","DOI":"10.1145\/1718487.1718518"},{"key":"B17","doi-asserted-by":"crossref","unstructured":"He X, Kempe D (2016) Robust influence maximization.\n                      Proc. 22nd ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining\n                      (Association for Computing Machinery, New York), 885\u2013894.","DOI":"10.1145\/2939672.2939760"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1145\/3233227"},{"key":"B19","unstructured":"Katariya S, Kveton B, Szepesvari C, Wen Z (2016) DCM bandits: Learning to rank with multiple clicks. Balcan MF, Weinberger KQ, eds.\n                      ICML\u201916: Proc. 33rd Internat. Conf. Machine Learn.\n                      , vol. 48 (PMLR, New York), 1215\u20131224."},{"key":"B20","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg J, Tardos \u00c9 (2003) Maximizing the spread of influence through a social network.\n                      KDD\u201903: Proc. 9th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining\n                      (Association for Computing Machinery, New York), 137\u2013146.","DOI":"10.1145\/956750.956769"},{"key":"B21","unstructured":"Kveton B, Szepesvari C, Wen Z, Ashkan A (2015) Cascading bandits: Learning to rank in the cascade model. Bach F, Blei D, eds.\n                      ICML\u201915: Proc. 32nd Internat. Conf. Machine Learn.\n                      , vol. 36 (PMLR, New York), 767\u2013776."},{"key":"B22","unstructured":"Kveton B, Wen Z, Ashkan A, Szepesvari C (2015a) Combinatorial cascading bandits. Cortes C, Lee DD, Sugiyama M, Garnett R, eds.\n                      NIPS\u201915: Proc. 29th Internat. Conf. Adv. Neural Inform. Processing Systems\n                      , vol. 1 (MIT Press, Cambridge, MA), 1450\u20131458."},{"key":"B23","unstructured":"Kveton B, Wen Z, Ashkan A, Szepesvari C (2015b) Tight regret bounds for stochastic combinatorial semi-bandits.\n                      Proc. 18th Internat. Conf. Intelligence Statist.\n                      (PMLR, New York), 535\u2013543."},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401"},{"key":"B25","doi-asserted-by":"crossref","unstructured":"Lei S, Maniu S, Mo L, Cheng R, Senellart P (2015) Online influence maximization.\n                      PKDD\u201915: Proc. 21st ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining\n                      (Association for Computing Machinery, New York), 645\u2013654.","DOI":"10.1145\/2783258.2783271"},{"key":"B26","unstructured":"Li L, Lu Y, Zhou D (2017) Provably optimal algorithms for generalized linear contextual bandits.\n                      Proc. 34th Internat. Conf. Machine Learn.\n                      , vol. 70 (PMLR, New York), 2071\u20132080."},{"key":"B27","unstructured":"Li S, Kong F, Tang K, Li Q, Chen W (2020) Online influence maximization under linear threshold model. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds.\n                      NIPS\u201920: Proc. 34th Internat. Conf. Adv. Neural Inform. Processing Systems\n                      (Curran Associates, Red Hook, NY), 1192\u20131204."},{"key":"B28","unstructured":"Mannor S, Shamir O (2011) From bandits to experts: On the value of side-observations. Shawe-Taylor J, Zemel RS, Bartlett PL, Pereira F, Weinberger KQ, eds.\n                      NIPS\u201911: Proc. 25th Internat. Conf. Adv. Neural Inform. Processing Systems\n                      (Curran Associates Inc. Red Hook, NY), 684\u2013692."},{"key":"B29","unstructured":"McAuley J, Leskovec J (2012) Learning to discover social circles in ego networks.\n                      NIPS\u201912: Proc. 26th Internat. Conf. Neural Inform. Processing Systems\n                      , vol. 1 (Curran Associates Inc., Red Hook, NY), 539\u2013547."},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254783"},{"key":"B32","doi-asserted-by":"crossref","unstructured":"Oh M-h, Iyengar G (2021) Multinomial logit contextual bandits: Provable optimality and practicality.\n                      Proc. AAAI Conf Artificial Intelligence\n                      , vol. 35 (AAAI Press, Washington, DC), 9205\u20139213.","DOI":"10.1609\/aaai.v35i10.17111"},{"key":"B33","doi-asserted-by":"crossref","unstructured":"Saito K, Nakano R, Kimura M (2008) Prediction of information diffusion probabilities for independent cascade model. Lovrek I, Howlett RJ, Jain LC, eds.\n                      Knowledge-Based Intelligent Inform. Engrg. Systems KES 2008,\n                      Lecture Notes in Computer Science, vol. 5179 (Springer, Berlin, Heidelberg), 67\u201375.","DOI":"10.1007\/978-3-540-85567-5_9"},{"key":"B34","doi-asserted-by":"crossref","unstructured":"Tang Y, Xiao X, Shi Y (2014) Influence maximization: Near-optimal time complexity meets practical efficiency.\n                      SIGMOD\u201914: Proc. 2014 ACM SIGMOD Internat. Conf. Management Data\n                      (Association for Computing Machinery, New York), 75\u201386.","DOI":"10.1145\/2588555.2593670"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805762"},{"key":"B36","unstructured":"Valko M (2016) Bandits on graphs and structures. Unpublished PhD thesis, \u00c9cole normale sup\u00e9rieure de Cachan (ENS Cachan), Paris."},{"key":"B37","unstructured":"Vaswani S, Duttachoudhury N (2013) Learning influence diffusion probabilities under the linear threshold model. Computer Science Department, University of British Columbia, Vancouver."},{"key":"B38","unstructured":"Vaswani S, Lakshmanan L, Schmidt M (2015) Influence maximization with bandits. Preprint, submitted February 27, https:\/\/arxiv.org\/abs\/1503.00024."},{"key":"B39","unstructured":"Wang Q, Chen W (2017) Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications. von Luxburg U, Guyon I, Bengio S, Wallach H, Fergus R, eds.\n                      NIPS\u201917: Proc. 31st Internat. Conf. Adv. Neural Inform. Processing Systems\n                      (Curran Associates Inc. Red Hook, NY), 1161\u20131171."},{"key":"B40","unstructured":"Wen Z, Kveton B, Valko M, Vaswani S (2017) Online influence maximization under independent cascade model with semi-bandit feedback. von Luxburg U, Guyon I, Bengio S, Wallach H, Fergus R, eds.\n                      NIPS\u201917: Proc. 31st Internat. Conf. Adv. Neural Inform. Processing Systems\n                      (Curran Associates Inc. Red Hook, NY), 3022\u20133032."},{"key":"B41","unstructured":"Yang S, Wang S, Truong V-A (2019) Online learning and optimization under a new linear-threshold model with negative influence. Preprint, submitted November 8, https:\/\/arxiv.org\/abs\/1911.03276."},{"key":"B42","unstructured":"Zong S, Ni H, Sung K, Ke NR, Wen Z, Kveton B (2016) Cascading bandits for large-scale recommendation problems. Ihler A, Janzing D, eds.\n                      UAI\u201916: Proc. 32nd Conf. Uncertainty Artificial Intelligence\n                      (AUAI Press, Arlington, VA), 835\u2013844."}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2021.0117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,14]],"date-time":"2026-08-14T08:43:07Z","timestamp":1786696987000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2021.0117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["10.1287\/moor.2021.0117"],"URL":"https:\/\/doi.org\/10.1287\/moor.2021.0117","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8]]}}}