{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T09:10:30Z","timestamp":1782378630122,"version":"3.54.5"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,7,30]],"date-time":"2022-07-30T00:00:00Z","timestamp":1659139200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["61902042"],"award-info":[{"award-number":["61902042"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005230","name":"Chongqing Natural Science Foundation","doi-asserted-by":"crossref","award":["cstc2020jcyj-msxmX0652"],"award-info":[{"award-number":["cstc2020jcyj-msxmX0652"]}],"id":[{"id":"10.13039\/501100005230","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Chongqing Talents: Exceptional Young Talents Project","award":["cstc2021ycjh-bgzxm0195"],"award-info":[{"award-number":["cstc2021ycjh-bgzxm0195"]}]},{"name":"GRF","award":["14201819"],"award-info":[{"award-number":["14201819"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>Contextual bandit serves as an invaluable tool to balance the<jats:italic>exploration vs. exploitation<\/jats:italic>tradeoff in various applications such as online recommendation. In many applications,<jats:italic>heterogeneous information networks<\/jats:italic>(HINs) provide rich side information for contextual bandits, such as different types of attributes and relationships among users and items. In this article, we propose the first HIN-assisted contextual bandit framework, which utilizes a given HIN to assist contextual bandit learning. The proposed framework uses meta-paths in HIN to extract rich relations among users and items for the contextual bandit. The main challenge is how to leverage these relations, since users\u2019 preference over items, the target of our online learning, are closely related to users\u2019 preference over meta-paths. However, it is unknown which meta-path a user prefers more. Thus, both preferences are needed to be learned in an online fashion with exploration vs. exploitation tradeoff balanced. We propose the HIN-assisted upper confidence bound (HUCB) algorithm to address such a challenge. For each meta-path, the HUCB algorithm employs an independent base bandit algorithm to handle online item recommendations by leveraging the relationship captured in this meta-path. A bandit master is then employed to learn users\u2019 preference over meta-paths to dynamically combine base bandit algorithms with a balance of exploration vs. exploitation tradeoff. We theoretically prove that the HUCB algorithm can achieve similar performance compared with the optimal algorithm where each user is served according to his true preference over meta-paths (assuming the optimal algorithm knows the preference). Moreover, we prove that the HUCB algorithm benefits from leveraging HIN in achieving a smaller regret upper bound than the baseline algorithm without leveraging HIN. Experimental results on a synthetic dataset, as well as real datasets from LastFM and Yelp demonstrate the fast learning speed of the HUCB algorithm.<\/jats:p>","DOI":"10.1145\/3522590","type":"journal-article","created":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T21:30:32Z","timestamp":1647379832000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Improving Bandit Learning Via Heterogeneous Information Networks: Algorithms and Applications"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3321-5940","authenticated-orcid":false,"given":"Xiaoying","family":"Zhang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Shatin, NT, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7466-0384","authenticated-orcid":false,"given":"Hong","family":"Xie","sequence":"additional","affiliation":[{"name":"Chongqing University, Shapingba, Chongqing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7935-7210","authenticated-orcid":false,"given":"John C. S.","family":"Lui","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shatin, NT, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,7,30]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"2312","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Abbasi-Yadkori Yasin","year":"2011","unstructured":"Yasin Abbasi-Yadkori, D\u00e1vid P\u00e1l, and Csaba Szepesv\u00e1ri. 2011. Improved algorithms for linear stochastic bandits. In Proceedings of the Advances in Neural Information Processing Systems. 2312\u20132320."},{"key":"e_1_3_2_3_2","first-page":"1638","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Agarwal Alekh","year":"2014","unstructured":"Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. 2014. Taming the monster: A fast and simple algorithm for contextual bandits. In Proceedings of the International Conference on Machine Learning. 1638\u20131646."},{"key":"e_1_3_2_4_2","unstructured":"Alekh Agarwal Haipeng Luo Behnam Neyshabur and Robert E. Schapire. 2017. Corralling a Band of Bandit Algorithms. In Proceedings of Annual Conference on Learning Theory . 12\u201338."},{"key":"e_1_3_2_5_2","first-page":"127","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Agrawal Shipra","year":"2013","unstructured":"Shipra Agrawal and Navin Goyal. 2013. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the International Conference on Machine Learning. 127\u2013135."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_3_2_7_2","first-page":"737","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Cesa-Bianchi Nicolo","year":"2013","unstructured":"Nicolo Cesa-Bianchi, Claudio Gentile, and Giovanni Zappella. 2013. A gang of bandits. In Proceedings of the Advances in Neural Information Processing Systems. 737\u2013745."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33013312"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1561\/1500000067"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.01.010"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3269278"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219965"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1126"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403050"},{"key":"e_1_3_2_15_2","first-page":"817","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Langford John","year":"2008","unstructured":"John Langford and Tong Zhang. 2008. The epoch-greedy algorithm for multi-armed bandits with side information. In Proceedings of the Advances in Neural Information Processing Systems. 817\u2013824."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772758"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935878"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/3305890.3305895"},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","unstructured":"Shuai Li Wei Chen Shuai Li and Kwong-Sak Leung. 2019. Improved algorithm on online clustering of bandits. In International Joint Conference on Artificial Intelligence . 2923\u20132929.","DOI":"10.24963\/ijcai.2019\/405"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2911451.2911548"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833443"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.2297920"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806528"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11739"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.2200\/S00433ED1V01Y201207DMK005"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402736"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/110843587"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3462810"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983847"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10936"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2911451.2911528"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556259"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939878"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098063"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3441446"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3185994"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330668"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371801"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3522590","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3522590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:33Z","timestamp":1750183773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3522590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,30]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3522590"],"URL":"https:\/\/doi.org\/10.1145\/3522590","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,30]]},"assertion":[{"value":"2021-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}