{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:41Z","timestamp":1750220081603,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2022,5,26]]},"abstract":"<jats:p>In this paper, we study the multi-scale expert problem, where the rewards of different experts vary in different reward ranges. The performance of existing algorithms for the multi-scale expert problem degrades linearly proportional to the maximum reward range of any expert or the best expert and does not capture the non-uniform heterogeneity in the reward ranges among experts. In this work, we propose learning algorithms that construct a hierarchical tree structure based on the heterogeneity of the reward range of experts and then determine differentiated learning rates based on the reward upper bounds and cumulative empirical feedback over time. We then characterize the regret of the proposed algorithms as a function of non-uniform reward ranges and show that their regrets outperform prior algorithms when the rewards of experts exhibit non-uniform heterogeneity in different ranges. Last, our numerical experiments verify our algorithms' efficiency compared to previous algorithms.<\/jats:p>","DOI":"10.1145\/3530900","type":"journal-article","created":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T17:16:18Z","timestamp":1654535778000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Hierarchical Learning Algorithms for Multi-scale Expert Problems"],"prefix":"10.1145","volume":"6","author":[{"given":"Lin","family":"Yang","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu-Zhen Janice","family":"Chen","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad H.","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Herbster","sequence":"additional","affiliation":[{"name":"University College London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Don","family":"Towsley","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Improved algorithms for linear stochastic bandits. 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. Advances in neural information processing systems , Vol. 24 ( 2011 ), 2312--2320. Yasin Abbasi-Yadkori, D\u00e1vid P\u00e1l, and Csaba Szepesv\u00e1ri. 2011. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems , Vol. 24 (2011), 2312--2320."},{"key":"e_1_2_1_2_1","series-title":"SIAM journal on control and optimization","volume-title":"The continuum-armed bandit problem","author":"Agrawal Rajeev","year":"1995","unstructured":"Rajeev Agrawal . 1995. The continuum-armed bandit problem . SIAM journal on control and optimization , Vol. 33 , 6 ( 1995 ), 1926--1951. Rajeev Agrawal. 1995. The continuum-armed bandit problem. SIAM journal on control and optimization , Vol. 33, 6 (1995), 1926--1951."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11894841_20"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_5_1","volume-title":"Prediction with corrupted expert advice. arXiv preprint arXiv:2002.10286","author":"Amir Idan","year":"2020","unstructured":"Idan Amir , Idan Attias , Tomer Koren , Roi Livni , and Yishay Mansour . 2020. Prediction with corrupted expert advice. arXiv preprint arXiv:2002.10286 ( 2020 ). Idan Amir, Idan Attias, Tomer Koren, Roi Livni, and Yishay Mansour. 2020. Prediction with corrupted expert advice. arXiv preprint arXiv:2002.10286 (2020)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72927-3_33"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00064"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.012"},{"key":"e_1_2_1_10_1","volume-title":"Multi-scale online learning and its applications to online auctions. arXiv preprint arXiv:1705.09700","author":"Bubeck S\u00e9bastien","year":"2017","unstructured":"S\u00e9bastien Bubeck , Nikhil R Devanur , Zhiyi Huang , and Rad Niazadeh . 2017a. Multi-scale online learning and its applications to online auctions. arXiv preprint arXiv:1705.09700 ( 2017 ). S\u00e9bastien Bubeck, Nikhil R Devanur, Zhiyi Huang, and Rad Niazadeh. 2017a. Multi-scale online learning and its applications to online auctions. arXiv preprint arXiv:1705.09700 (2017)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085145"},{"key":"e_1_2_1_12_1","volume-title":"Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 42--1.","author":"Bubeck S\u00e9bastien","year":"2012","unstructured":"S\u00e9bastien Bubeck and Aleksandrs Slivkins . 2012 . The best of both worlds: Stochastic and adversarial bandits . In Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 42--1. S\u00e9bastien Bubeck and Aleksandrs Slivkins. 2012. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 42--1."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258179"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5001-7"},{"key":"e_1_2_1_15_1","unstructured":"Kamalika Chaudhuri Yoav Freund and Daniel J Hsu. 2009. A parameter-free hedging algorithm. In Advances in neural information processing systems. 297--305.  Kamalika Chaudhuri Yoav Freund and Daniel J Hsu. 2009. A parameter-free hedging algorithm. In Advances in neural information processing systems. 297--305."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0738"},{"key":"e_1_2_1_18_1","volume-title":"Introduction to online convex optimization. arXiv preprint arXiv:1909.05207","author":"Hazan Elad","year":"2019","unstructured":"Elad Hazan . 2019. Introduction to online convex optimization. arXiv preprint arXiv:1909.05207 ( 2019 ). Elad Hazan. 2019. Introduction to online convex optimization. arXiv preprint arXiv:1909.05207 (2019)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30215-5_22"},{"key":"e_1_2_1_20_1","first-page":"697","article-title":"Nearly tight bounds for the continuum-armed bandit problem","volume":"17","author":"Kleinberg Robert","year":"2004","unstructured":"Robert Kleinberg . 2004 . Nearly tight bounds for the continuum-armed bandit problem . Advances in Neural Information Processing Systems , Vol. 17 (2004), 697 -- 704 . Robert Kleinberg. 2004. Nearly tight bounds for the continuum-armed bandit problem. Advances in Neural Information Processing Systems , Vol. 17 (2004), 697--704.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374475"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299873"},{"key":"e_1_2_1_24_1","volume-title":"International Conference on Machine Learning . PMLR, 824--832","author":"Krichene Walid","year":"2015","unstructured":"Walid Krichene , Maximilian Balandat , Claire Tomlin , and Alexandre Bayen . 2015 . The hedge algorithm on a continuum . In International Conference on Machine Learning . PMLR, 824--832 . Walid Krichene, Maximilian Balandat, Claire Tomlin, and Alexandre Bayen. 2015. The hedge algorithm on a continuum. In International Conference on Machine Learning . PMLR, 824--832."},{"key":"e_1_2_1_25_1","volume-title":"The weighted majority algorithm. Information and computation","author":"Littlestone Nick","year":"1994","unstructured":"Nick Littlestone and Manfred K Warmuth . 1994. The weighted majority algorithm. Information and computation , Vol. 108 , 2 ( 1994 ), 212--261. Nick Littlestone and Manfred K Warmuth. 1994. The weighted majority algorithm. Information and computation , Vol. 108, 2 (1994), 212--261."},{"key":"e_1_2_1_26_1","first-page":"1368","article-title":"A drifting-games analysis for online learning and applications to boosting","volume":"27","author":"Luo Haipeng","year":"2014","unstructured":"Haipeng Luo and Robert E Schapire . 2014 . A drifting-games analysis for online learning and applications to boosting . Advances in Neural Information Processing Systems , Vol. 27 (2014), 1368 -- 1376 . Haipeng Luo and Robert E Schapire. 2014. A drifting-games analysis for online learning and applications to boosting. Advances in Neural Information Processing Systems , Vol. 27 (2014), 1368--1376.","journal-title":"Advances in Neural Information Processing Systems"},{"volume-title":"Joint european conference on machine learning and knowledge discovery in databases","author":"Maillard Odalric-Ambrym","key":"e_1_2_1_27_1","unstructured":"Odalric-Ambrym Maillard and R\u00e9mi Munos . 2010. Online learning in adversarial lipschitz environments . In Joint european conference on machine learning and knowledge discovery in databases . Springer , 305--320. Odalric-Ambrym Maillard and R\u00e9mi Munos. 2010. Online learning in adversarial lipschitz environments. In Joint european conference on machine learning and knowledge discovery in databases. Springer, 305--320."},{"key":"e_1_2_1_28_1","first-page":"1","article-title":"On the optimality of the Hedge algorithm in the stochastic regime","volume":"20","author":"Mourtada Jaouad","year":"2019","unstructured":"Jaouad Mourtada and St\u00e9phane Ga\"iffas. 2019 . On the optimality of the Hedge algorithm in the stochastic regime . Journal of Machine Learning Research , Vol. 20 (2019), 1 -- 28 . Jaouad Mourtada and St\u00e9phane Ga\"iffas. 2019. On the optimality of the Hedge algorithm in the stochastic regime. Journal of Machine Learning Research , Vol. 20 (2019), 1--28.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_29_1","volume-title":"Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits. In Conference on Learning Theory. PMLR, 3227--3249","author":"Rouyer Chlo\u00e9","year":"2020","unstructured":"Chlo\u00e9 Rouyer and Yevgeny Seldin . 2020 . Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits. In Conference on Learning Theory. PMLR, 3227--3249 . Chlo\u00e9 Rouyer and Yevgeny Seldin. 2020. Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits. In Conference on Learning Theory. PMLR, 3227--3249."},{"key":"e_1_2_1_30_1","volume-title":"International Conference on Machine Learning. PMLR, 1287--1295","author":"Seldin Yevgeny","year":"2014","unstructured":"Yevgeny Seldin and Aleksandrs Slivkins . 2014 . One practical algorithm for both stochastic and adversarial bandits . In International Conference on Machine Learning. PMLR, 1287--1295 . Yevgeny Seldin and Aleksandrs Slivkins. 2014. One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning. PMLR, 1287--1295."},{"key":"e_1_2_1_31_1","first-page":"13624","article-title":"No-regret learning in unknown games with correlated payoffs","volume":"32","author":"Sessa Pier Giuseppe","year":"2019","unstructured":"Pier Giuseppe Sessa , Ilija Bogunovic , Maryam Kamgarpour , and Andreas Krause . 2019 . No-regret learning in unknown games with correlated payoffs . Advances in Neural Information Processing Systems , Vol. 32 (2019), 13624 -- 13633 . Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause. 2019. No-regret learning in unknown games with correlated payoffs. Advances in Neural Information Processing Systems , Vol. 32 (2019), 13624--13633.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_32_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 3567--3577","author":"Sharma Dravyansh","year":"2020","unstructured":"Dravyansh Sharma , Maria-Florina Balcan , and Travis Dick . 2020 . Learning piecewise Lipschitz functions in changing environments . In International Conference on Artificial Intelligence and Statistics. PMLR, 3567--3577 . Dravyansh Sharma, Maria-Florina Balcan, and Travis Dick. 2020. Learning piecewise Lipschitz functions in changing environments. In International Conference on Artificial Intelligence and Statistics. PMLR, 3567--3577."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 24th annual Conference On Learning Theory. JMLR Workshop and Conference Proceedings, 679--702","author":"Slivkins Aleksandrs","year":"2011","unstructured":"Aleksandrs Slivkins . 2011 . Contextual bandits with similarity information . In Proceedings of the 24th annual Conference On Learning Theory. JMLR Workshop and Conference Proceedings, 679--702 . Aleksandrs Slivkins. 2011. Contextual bandits with similarity information. In Proceedings of the 24th annual Conference On Learning Theory. JMLR Workshop and Conference Proceedings, 679--702."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1556"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-146-8.50032-1"},{"key":"e_1_2_1_36_1","article-title":"Online Learning in Case of Unbounded Losses Using Follow the Perturbed Leader Algorithm","volume":"12","author":"V'yugin Vladimir V","year":"2011","unstructured":"Vladimir V V'yugin . 2011 . Online Learning in Case of Unbounded Losses Using Follow the Perturbed Leader Algorithm . Journal of Machine Learning Research , Vol. 12 , 1 (2011). Vladimir V V'yugin. 2011. Online Learning in Case of Unbounded Losses Using Follow the Perturbed Leader Algorithm. Journal of Machine Learning Research , Vol. 12, 1 (2011).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3224420"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530900","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3530900","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:27Z","timestamp":1750183767000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530900"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,5,26]]}},"alternative-id":["10.1145\/3530900"],"URL":"https:\/\/doi.org\/10.1145\/3530900","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"2022-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}