{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T14:49:59Z","timestamp":1776350999484,"version":"3.51.2"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T00:00:00Z","timestamp":1638230400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM\/IMS Trans. Data Sci."],"published-print":{"date-parts":[[2021,11,30]]},"abstract":"<jats:p>\n                    There are numerous real-world problems where a user must make decisions under uncertainty. For the problem of\n                    <jats:italic toggle=\"yes\">influence maximization<\/jats:italic>\n                    on a social network, for example, the user must select a set of\n                    <jats:italic toggle=\"yes\">K<\/jats:italic>\n                    influencers who will jointly have a large influence on many users. With the lack of prior knowledge about the diffusion process or even topological information, this problem becomes quite challenging. This problem can be cast as a combinatorial bandit problem, where the user can repeatedly choose a candidate set of\n                    <jats:italic toggle=\"yes\">K<\/jats:italic>\n                    out of\n                    <jats:italic toggle=\"yes\">N<\/jats:italic>\n                    arms at each time, with an aim to achieve an efficient trade-off between exploration and exploitation.\n                  <\/jats:p>\n                  <jats:p>\n                    In this work, we present the first combinatorial bandit algorithm for which the only feedback is a non-linear reward of the selected\n                    <jats:italic toggle=\"yes\">K<\/jats:italic>\n                    arms. No other feedback is needed. In the context of influence maximization, this means no feedback in the form of which nodes or edges were activated needs to be available, just the amount of influence. The novel algorithm we propose, CMAB-SM, is based on a divide-and-conquer strategy. It is computationally and storage efficient. Over a time horizon\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    , the proposed algorithm achieves a\n                    <jats:italic toggle=\"yes\">regret bound<\/jats:italic>\n                    of \u00d5(\n                    <jats:italic toggle=\"yes\">K<\/jats:italic>\n                    <jats:sup>1\/2<\/jats:sup>\n                    <jats:italic toggle=\"yes\">N<\/jats:italic>\n                    <jats:sup>1\/3<\/jats:sup>\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    <jats:sup>2\/3<\/jats:sup>\n                    ). This bound is sub-linear in all of the parameters:\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    ,\n                    <jats:italic toggle=\"yes\">N<\/jats:italic>\n                    , and\n                    <jats:italic toggle=\"yes\">K<\/jats:italic>\n                    .\n                  <\/jats:p>\n                  <jats:p>We empirically demonstrate our algorithm\u2019s performance using the applications of influence maximization and product cross-selling. For influence maximization, we provide experiments on real-world social networks, showing that the proposed CMAB algorithm outperforms bandit-specific and social-influence-domain-specific algorithms in terms of empirical run-time and expected influence. For product cross-selling, we also demonstrate that the proposed CMAB algorithm outperforms considered baselines on synthetic data.<\/jats:p>","DOI":"10.1145\/3507787","type":"journal-article","created":{"date-parts":[[2022,2,3]],"date-time":"2022-02-03T09:01:36Z","timestamp":1643878896000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Stochastic Top\n                    <i>K<\/i>\n                    -Subset Bandits with Linear Space and Non-Linear Feedback with Applications to Social Influence Maximization"],"prefix":"10.1145","volume":"2","author":[{"given":"Mridul","family":"Agarwal","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9131-4723","authenticated-orcid":false,"given":"Vaneet","family":"Aggarwal","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhishek K.","family":"Umrawal","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher J.","family":"Quinn","sequence":"additional","affiliation":[{"name":"Iowa State University, Ames, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,2,3]]},"reference":[{"key":"e_1_3_12_2_2","first-page":"2312","volume-title":"Advances in Neural Information Processing Systems 24","author":"Abbasi-Yadkori Yasin","year":"2011","unstructured":"Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari. 2011. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24. 2312\u20132320."},{"key":"e_1_3_12_3_2","article-title":"Regret bounds for stochastic combinatorial multi-armed bandits with linear space complexity","author":"Agarwal Mridul","year":"2018","unstructured":"Mridul Agarwal and Vaneet Aggarwal. 2018. Regret bounds for stochastic combinatorial multi-armed bandits with linear space complexity. arXiv preprint arXiv:1811.11925 (2018).","journal-title":"arXiv preprint arXiv:1811.11925"},{"key":"e_1_3_12_4_2","volume-title":"Proc. AAAI","author":"Agarwal Mridul","year":"2021","unstructured":"Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, and Abhishek Umrawal. 2021. DART: aDaptive accept reject for non-linear top-k subset identification. In Proc. AAAI."},{"key":"e_1_3_12_5_2","first-page":"306","volume-title":"Algorithmic Learning Theory","author":"Agarwal Mridul","year":"2021","unstructured":"Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, and Abhishek K. Umrawal. 2021. Stochastic Top- K subset bandits with linear space and non-linear feedback. In Algorithmic Learning Theory. PMLR, 306\u2013339."},{"key":"e_1_3_12_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0598"},{"key":"e_1_3_12_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10998-010-3055-6"},{"key":"e_1_3_12_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-405X(75)90025-2"},{"key":"e_1_3_12_9_2","article-title":"What doubling tricks can and can\u2019t do for multi-armed bandits","author":"Besson Lilian","year":"2018","unstructured":"Lilian Besson and Emilie Kaufmann. 2018. What doubling tricks can and can\u2019t do for multi-armed bandits. arXiv.org (2018).","journal-title":"arXiv.org"},{"key":"e_1_3_12_10_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_3_12_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.01.001"},{"key":"e_1_3_12_12_2","series-title":"Proceedings of Machine Learning Research","first-page":"151","volume-title":"Proceedings of the 30th International Conference on Machine Learning","volume":"28","author":"Chen Wei","year":"2013","unstructured":"Wei Chen, Yajun Wang, and Yang Yuan. 2013. Combinatorial multi-armed bandit: General framework and applications. In Proceedings of the 30th International Conference on Machine Learning(Proceedings of Machine Learning Research, Vol. 28), Sanjoy Dasgupta and David McAllester (Eds.). PMLR, Atlanta, Georgia, USA, 151\u2013159. http:\/\/proceedings.mlr.press\/v28\/chen13a.html."},{"key":"e_1_3_12_13_2","first-page":"355","volume-title":"Proceedings of the 21st Annual Conference on Learning Theory","author":"Dani Varsha","year":"2008","unstructured":"Varsha Dani, Thomas Hayes, and Sham Kakade. 2008. Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Annual Conference on Learning Theory. 355\u2013366."},{"key":"e_1_3_12_14_2","first-page":"355","volume-title":"21st Annual Conference on Learning Theory - COLT 2008, Helsinki, Finland, July 9-12, 2008","author":"Dani Varsha","year":"2008","unstructured":"Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. 2008. Stochastic linear optimization under bandit feedback. In 21st Annual Conference on Learning Theory - COLT 2008, Helsinki, Finland, July 9-12, 2008, Rocco A. Servedio and Tong Zhang (Eds.). Omnipress, 355\u2013366. http:\/\/colt2008.cs.helsinki.fi\/papers\/80-Dani.pdf."},{"key":"e_1_3_12_15_2","first-page":"345","volume-title":"Advances in Neural Information Processing Systems 20","author":"Dani Varsha","year":"2008","unstructured":"Varsha Dani, Sham M. Kakade, and Thomas P. Hayes. 2008. The price of bandit information for online optimization. In Advances in Neural Information Processing Systems 20, J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis (Eds.). Curran Associates, Inc., 345\u2013352."},{"key":"e_1_3_12_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_3_12_17_2","first-page":"586","volume-title":"Advances in Neural Information Processing Systems 23","author":"Filippi Sarah","year":"2010","unstructured":"Sarah Filippi, Olivier Cappe, Aurelien Garivier, and Csaba Szepesvari. 2010. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems 23. 586\u2013594."},{"key":"e_1_3_12_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/DYSPAN.2010.5457857"},{"key":"e_1_3_12_19_2","first-page":"100","volume-title":"Proceedings of the 31st International Conference on Machine Learning","author":"Gopalan Aditya","year":"2014","unstructured":"Aditya Gopalan, Shie Mannor, and Yishay Mansour. 2014. Thompson sampling for complex online problems. In Proceedings of the 31st International Conference on Machine Learning. 100\u2013108."},{"key":"e_1_3_12_20_2","article-title":"Credit Distribution Source Code Release","author":"Goyal Amit","year":"2011","unstructured":"Amit Goyal. 2011. Credit Distribution Source Code Release. https:\/\/www.cs.ubc.ca\/ goyal\/code-release.php. Accessed: 2019-04-10.","journal-title":"https:\/\/www.cs.ubc.ca\/ goyal\/code-release.php"},{"key":"e_1_3_12_21_2","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047492"},{"issue":"1","key":"e_1_3_12_22_2","first-page":"25","article-title":"Rules for ordering uncertain prospects","volume":"59","author":"Hadar Josef","year":"1969","unstructured":"Josef Hadar and William R. Russell. 1969. Rules for ordering uncertain prospects. The American Economic Review 59, 1 (1969), 25\u201334.","journal-title":"The American Economic Review"},{"key":"e_1_3_12_23_2","first-page":"98","volume-title":"Advances in Neural Information Processing Systems 30","author":"Jun Kwang-Sung","year":"2017","unstructured":"Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. 2017. Scalable generalized linear bandits: Online computation and hashing. In Advances in Neural Information Processing Systems 30. 98\u2013108."},{"key":"e_1_3_12_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_12_25_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1969.10501022"},{"key":"e_1_3_12_26_2","article-title":"BubbleRank: Safe online learning to rerank","author":"Kveton Branislav","year":"2018","unstructured":"Branislav Kveton, Chang Li, Tor Lattimore, Ilya Markov, Maarten de Rijke, Csaba Szepesvari, and Masrour Zoghi. 2018. BubbleRank: Safe online learning to rerank. arXiv preprint arXiv:1806.05819 (2018).","journal-title":"arXiv preprint arXiv:1806.05819"},{"key":"e_1_3_12_27_2","series-title":"Proceedings of Machine Learning Research","first-page":"767","volume-title":"Proceedings of the 32nd International Conference on Machine Learning","volume":"37","author":"Kveton Branislav","year":"2015","unstructured":"Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. 2015. Cascading bandits: Learning to rank in the cascade model. In Proceedings of the 32nd International Conference on Machine Learning(Proceedings of Machine Learning Research, Vol. 37), Francis Bach and David Blei (Eds.). PMLR, Lille, France, 767\u2013776. http:\/\/proceedings.mlr.press\/v37\/kveton15.html."},{"key":"e_1_3_12_28_2","article-title":"Matroid bandits: Fast combinatorial optimization with learning","author":"Kveton Branislav","year":"2014","unstructured":"Branislav Kveton, Zheng Wen, Azin Ashkan, Hoda Eydgahi, and Brian Eriksson. 2014. Matroid bandits: Fast combinatorial optimization with learning. arXiv preprint arXiv:1403.5045 (2014).","journal-title":"arXiv preprint arXiv:1403.5045"},{"key":"e_1_3_12_29_2","first-page":"535","volume-title":"Artificial Intelligence and Statistics","author":"Kveton Branislav","year":"2015","unstructured":"Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. 2015. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics. 535\u2013543."},{"key":"e_1_3_12_30_2","volume-title":"23rd International Conference on Artificial Intelligence and Statistics","author":"Kveton Branislav","year":"2020","unstructured":"Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. 2020. Randomized exploration in generalized linear bandits. In 23rd International Conference on Artificial Intelligence and Statistics."},{"key":"e_1_3_12_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783271"},{"key":"e_1_3_12_32_2","first-page":"539","volume-title":"Advances in Neural Information Processing Systems","author":"Leskovec Jure","year":"2012","unstructured":"Jure Leskovec and Julian J. Mcauley. 2012. Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems. 539\u2013547."},{"key":"e_1_3_12_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772758"},{"key":"e_1_3_12_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/3305890.3305895"},{"key":"e_1_3_12_35_2","series-title":"Proceedings of Machine Learning Research","first-page":"386","volume-title":"Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics","volume":"84","author":"Liau David","year":"2018","unstructured":"David Liau, Zhao Song, Eric Price, and Ger Yang. 2018. Stochastic multi-armed bandits in constant space. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics(Proceedings of Machine Learning Research, Vol. 84), Amos Storkey and Fernando Perez-Cruz (Eds.). PMLR, Playa Blanca, Lanzarote, Canary Islands, 386\u2013394. http:\/\/proceedings.mlr.press\/v84\/liau18a.html."},{"key":"e_1_3_12_36_2","series-title":"Proceedings of Machine Learning Research","first-page":"901","volume-title":"Proceedings of the 31st International Conference on Machine Learning","volume":"32","author":"Lin Tian","year":"2014","unstructured":"Tian Lin, Bruno Abrahao, Robert Kleinberg, John Lui, and Wei Chen. 2014. Combinatorial partial monitoring game with linear feedback and its applications. In Proceedings of the 31st International Conference on Machine Learning(Proceedings of Machine Learning Research, Vol. 32), Eric P. Xing and Tony Jebara (Eds.). PMLR, Bejing, China, 901\u2013909. http:\/\/proceedings.mlr.press\/v32\/lind14.html."},{"key":"e_1_3_12_37_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11888"},{"key":"e_1_3_12_38_2","first-page":"752","volume-title":"Algorithmic Learning Theory","author":"Rejwan Idan","year":"2020","unstructured":"Idan Rejwan and Yishay Mansour. 2020. Top- k combinatorial bandits with full-bandit feedback. In Algorithmic Learning Theory. 752\u2013776."},{"key":"e_1_3_12_39_2","volume-title":"Introduction to Combinatorics","author":"Slomson Alan B.","year":"1997","unstructured":"Alan B. Slomson. 1997. Introduction to Combinatorics. CRC Press."},{"key":"e_1_3_12_40_2","doi-asserted-by":"publisher","DOI":"10.5555\/3305890.3306046"},{"key":"e_1_3_12_41_2","article-title":"Online influence maximization under independent cascade model with semi-bandit feedback","author":"Wen Zheng","year":"2016","unstructured":"Zheng Wen, Branislav Kveton, Michal Valko, and Sharan Vaswani. 2016. Online influence maximization under independent cascade model with semi-bandit feedback. arXiv preprint arXiv:1605.06593 (2016).","journal-title":"arXiv preprint arXiv:1605.06593"},{"key":"e_1_3_12_42_2","first-page":"3022","volume-title":"Advances in Neural Information Processing Systems","author":"Wen Zheng","year":"2017","unstructured":"Zheng Wen, Branislav Kveton, Michal Valko, and Sharan Vaswani. 2017. Online influence maximization under independent cascade model with semi-bandit feedback. In Advances in Neural Information Processing Systems. 3022\u20133032."},{"key":"e_1_3_12_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2003.1250942"},{"key":"e_1_3_12_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2015.2466453"},{"key":"e_1_3_12_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339716"},{"key":"e_1_3_12_46_2","article-title":"Online influence maximization with node-level feedback using standard offline oracles","author":"Zhang Zhijie","year":"2021","unstructured":"Zhijie Zhang, Wei Chen, Xiaoming Sun, and Jialin Zhang. 2021. Online influence maximization with node-level feedback using standard offline oracles. arXiv preprint arXiv:2109.06077 (2021).","journal-title":"arXiv preprint arXiv:2109.06077"}],"container-title":["ACM\/IMS Transactions on Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3507787","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3507787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T13:55:58Z","timestamp":1776347758000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3507787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,30]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,11,30]]}},"alternative-id":["10.1145\/3507787"],"URL":"https:\/\/doi.org\/10.1145\/3507787","relation":{},"ISSN":["2691-1922"],"issn-type":[{"value":"2691-1922","type":"print"}],"subject":[],"published":{"date-parts":[[2021,11,30]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}