{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:08:45Z","timestamp":1764688125055,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T00:00:00Z","timestamp":1734480000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T00:00:00Z","timestamp":1734480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["101104278","101104278"],"award-info":[{"award-number":["101104278","101104278"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In this paper, we investigate Thompson sampling-based sequential block elimination approaches for dynamic assignment problems in a pure-exploration Multi-Armed Bandit (MAB) setting with limited budget constraints. The problem can be considered as a bandit game-play between the environment and a decision-maker in a metric space. Many instances of problems in fields such as e-commerce, logistics, mobility management, data management and operations research can be framed as dynamic assignment problems with budget constraints. Given an <jats:italic>l<\/jats:italic>-dimensional action space representing <jats:italic>l<\/jats:italic> variants of an entity and a budget for exploring the action space, the optimal dynamic assignment problem refers to the task of identifying the values to be assigned to different variants of the entity that maximizes the total reward by utilizing at most the given budget of rounds of play. We contribute a class of block elimination-based MAB algorithms specifically designed for the dynamic assignment problem with limited budget. Our algorithms begin by discretizing the continuous action space into a finite set of discrete actions, then proceed with a recursive block elimination procedure to remove sub-optimal actions. The elimination is carried out by calculating confidence bounds over blocks of actions. We explore two different confidence bound estimation techniques. We perform comprehensive experiments on two problem instances from distributed data management and logistics. Our results showcase that our approach yields a lower misidentification probability (i.e., the probability of recommending a non-optimal action) compared to state-of-the-art elimination-based pure-exploration MAB algorithms.<\/jats:p>","DOI":"10.1007\/s10618-024-01083-2","type":"journal-article","created":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T12:48:33Z","timestamp":1734526113000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Thompson sampling-based recursive block elimination for dynamic assignment under limited budget in pure-exploration"],"prefix":"10.1007","volume":"39","author":[{"given":"Shameem Puthiya","family":"Parambath","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Anagnostopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saleh Abdullah M.","family":"Alfahad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,18]]},"reference":[{"key":"1083_CR1","unstructured":"(2023) Closed-Loop Data Science Interaction with Probabilistic Models. https:\/\/www.gla.ac.uk\/schools\/computing\/research\/researchsections\/ida-section\/closedloop\/. Accessed: 2023-11-29"},{"key":"1083_CR2","unstructured":"Agrawal S, Goyal N (2012) Analysis of thompson sampling for the multi-armed bandit problem. In: Conference on Learning Theory, 39\u20131. JMLR Workshop and Conference Proceedings"},{"key":"1083_CR3","unstructured":"Agrawal S, Goyal N (2013) Thompson sampling for contextual bandits with linear payoffs. In: International Conference on Machine Learning, pp. 127\u2013135. PMLR"},{"key":"1083_CR4","unstructured":"Audibert J-Y, Bubeck S (2010) Best arm identification in multi-armed bandits. In: COLT-23th Conference on Learning Theory-2010, p. 13"},{"key":"1083_CR5","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1023\/A:1013689704352","volume":"2","author":"P Auer","year":"2002","unstructured":"Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time analysis of the multiarmed bandit problem. Mach Learn 2:235\u2013256","journal-title":"Mach Learn"},{"issue":"1","key":"1083_CR6","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0097539701398375","volume":"32","author":"P Auer","year":"2002","unstructured":"Auer P, Cesa-Bianchi N, Freund Y, Schapire RE (2002) The nonstochastic multiarmed bandit problem. SIAM J Comput 32(1):48\u201377","journal-title":"SIAM J Comput"},{"key":"1083_CR7","doi-asserted-by":"crossref","unstructured":"Ban Y, He J (2020) Generic outlier detection in multi-armed bandit. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 913\u2013923","DOI":"10.1145\/3394486.3403134"},{"issue":"3","key":"1083_CR8","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/j.jretai.2016.02.003","volume":"92","author":"E Breugelmans","year":"2016","unstructured":"Breugelmans E, Campo K (2016) Cross-channel effects of price promotions: an empirical analysis of the multi-channel grocery retail sector. J Retail 92(3):333\u2013351","journal-title":"J Retail"},{"issue":"19","key":"1083_CR9","doi-asserted-by":"publisher","first-page":"1832","DOI":"10.1016\/j.tcs.2010.12.059","volume":"412","author":"S Bubeck","year":"2011","unstructured":"Bubeck S, Munos R, Stoltz G (2011) Pure exploration in finitely-armed and continuous-armed bandits. Theoret Comput Sci 412(19):1832\u20131852","journal-title":"Theoret Comput Sci"},{"key":"1083_CR10","unstructured":"Bubeck S, Munos R, Stoltz G, Szepesv\u00e1ri C (2011) X-armed bandits. J Mach Learn Res 12(5)"},{"key":"1083_CR11","unstructured":"Carpentier A, Locatelli A (2016) Tight (lower) bounds for the fixed budget best arm identification bandit problem. In: Conference on Learning Theory, pp. 590\u2013604. PMLR"},{"key":"1083_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921","volume-title":"Prediction, Learning, and Games","author":"N Cesa-Bianchi","year":"2006","unstructured":"Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games. Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9780511546921"},{"key":"1083_CR13","unstructured":"Chapelle O, Li L (2011) An empirical evaluation of thompson sampling. Adv Neural Inf Process Syst 24"},{"key":"1083_CR14","doi-asserted-by":"crossref","unstructured":"Chawla S, Gionis A (2013) k-means\u2013: A unified approach to clustering and outlier detection. In: Proceedings of the 2013 SIAM International Conference on Data Mining, pp. 189\u2013197. SIAM","DOI":"10.1137\/1.9781611972832.21"},{"key":"1083_CR15","unstructured":"Coquelin P-A, Munos R (2007) Bandit algorithms for tree search. In: Uncertainty in Artificial Intelligence"},{"key":"1083_CR16","unstructured":"Faella M, Finzi A, Sauro L (2020) Rapidly finding the best arm using variance. In: ECAI 2020, pp. 2585\u20132591. IOS Press"},{"key":"1083_CR17","unstructured":"Gabillon V, Ghavamzadeh M, Lazaric A (2012) Best arm identification: A unified approach to fixed budget and fixed confidence. Adv Neural Inf Process Syst 25"},{"issue":"6","key":"1083_CR18","doi-asserted-by":"publisher","first-page":"1764","DOI":"10.1093\/jeea\/jvx050","volume":"16","author":"Y Gorodnichenko","year":"2018","unstructured":"Gorodnichenko Y, Sheremirov V, Talavera O (2018) Price setting in online markets: Does it click? J Eur Econ Assoc 16(6):1764\u20131811","journal-title":"J Eur Econ Assoc"},{"issue":"1","key":"1083_CR19","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.jretai.2018.10.003","volume":"95","author":"GTM Hult","year":"2019","unstructured":"Hult GTM, Sharma PN, Morgeson FV III, Zhang Y (2019) Antecedents and consequences of customer satisfaction: do they differ across online and offline purchases? J Retail 95(1):10\u201323","journal-title":"J Retail"},{"key":"1083_CR20","unstructured":"Jamieson K, Talwalkar A (2016) Non-stochastic best arm identification and hyperparameter optimization. In: Artificial Intelligence and Statistics, pp. 240\u2013248 . PMLR"},{"key":"1083_CR21","doi-asserted-by":"crossref","unstructured":"Jiang Z, Xu Y, Xu H, Wang Z, Qiao C, Zhao Y (2022) Fedmp: Federated learning through adaptive model pruning in heterogeneous edge computing. In: 2022 IEEE 38th International Conference on Data Engineering (ICDE), pp. 767\u2013779 . IEEE","DOI":"10.1109\/ICDE53745.2022.00062"},{"key":"1083_CR22","first-page":"26791","volume":"35","author":"M Jourdan","year":"2022","unstructured":"Jourdan M, Degenne R, Baudry D, Heide R, Kaufmann E (2022) Top two algorithms revisited. Adv Neural Inf Process Syst 35:26791\u201326803","journal-title":"Adv Neural Inf Process Syst"},{"key":"1083_CR23","unstructured":"Karnin Z, Koren T, Somekh O (2013) Almost optimal exploration in multi-armed bandits. In: International Conference on Machine Learning, pp. 1238\u20131246 . PMLR"},{"issue":"4","key":"1083_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3299873","volume":"66","author":"R Kleinberg","year":"2019","unstructured":"Kleinberg R, Slivkins A, Upfal E (2019) Bandits and experts in metric spaces. J ACM 66(4):1\u201377","journal-title":"J ACM"},{"key":"1083_CR25","doi-asserted-by":"crossref","unstructured":"Kleinberg R, Slivkins A, Upfal E (2008) Multi-armed bandits in metric spaces. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 681\u2013690","DOI":"10.1145\/1374376.1374475"},{"key":"1083_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401","volume-title":"Bandit Algorithms","author":"T Lattimore","year":"2020","unstructured":"Lattimore T, Szepesv\u00e1ri C (2020) Bandit Algorithms. Cambridge University Press. https:\/\/doi.org\/10.1017\/9781108571401"},{"key":"1083_CR27","doi-asserted-by":"crossref","unstructured":"Li L, Chu W, Langford J, Schapire RE (2010) A contextual-bandit approach to personalized news article recommendation. In: Proceedings of the 19th International Conference on World Wide Web, pp. 661\u2013670","DOI":"10.1145\/1772690.1772758"},{"key":"1083_CR28","doi-asserted-by":"crossref","unstructured":"Long Q, Anagnostopoulos C, Parambath SP, Bi D (2023) Feddip: Federated learning with extreme dynamic pruning and incremental regularization. In: 2023 IEEE International Conference on Data Mining (ICDM), pp. 1187\u20131192. IEEE","DOI":"10.1109\/ICDM58522.2023.00146"},{"key":"1083_CR29","first-page":"37445","volume":"35","author":"Y Luo","year":"2022","unstructured":"Luo Y, Sun WW, Liu Y (2022) Contextual dynamic pricing with unknown noise: Explore-then-ucb strategy and improved regrets. Adv Neural Inf Process Syst 35:37445\u201337457","journal-title":"Adv Neural Inf Process Syst"},{"key":"1083_CR30","unstructured":"Luo Y, Sun WW et al (2021) Distribution-free contextual dynamic pricing. arXiv preprint arXiv:2109.07340"},{"key":"1083_CR31","unstructured":"Magureanu S, Combes R, Proutiere A (2014) Lipschitz bandits: Regret lower bound and optimal algorithms. In: Conference on Learning Theory, pp. 975\u2013999. PMLR"},{"key":"1083_CR32","unstructured":"McMahan HB, Streeter M (2009) Tighter bounds for multi-armed bandits with expert advice. In: Proceedings of the 22nd Annual Conference on Learning Theory (COLT)"},{"key":"1083_CR33","unstructured":"McMahan B, Moore E, Ramage D, Hampson S, Arcas BA (2017)Communication-efficient learning of deep networks from decentralized data. In: Artificial Intelligence and Statistics, pp. 1273\u20131282. PMLR"},{"issue":"2","key":"1083_CR34","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1287\/mksc.2018.1129","volume":"38","author":"K Misra","year":"2019","unstructured":"Misra K, Schwartz EM, Abernethy J (2019) Dynamic online pricing with incomplete information using multiarmed bandit experiments. Mark Sci 38(2):226\u2013252","journal-title":"Mark Sci"},{"key":"1083_CR35","unstructured":"Mueller JW, Syrgkanis V, Taddy M (2019) Low-rank bandit methods for high-dimensional dynamic pricing. Adv Neural Inf Process Syst 32"},{"key":"1083_CR36","doi-asserted-by":"crossref","unstructured":"Mussi M, Genalti G, Trov\u00f2 F, Nuara A, Gatti N, Restelli M (2022) Pricing the long tail by explainable product aggregation and monotonic bandits. In: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3623\u20133633","DOI":"10.1145\/3534678.3539142"},{"key":"1083_CR37","unstructured":"Podimata C, Slivkins A (2021) Adaptive discretization for adversarial lipschitz bandits. In: Conference on Learning Theory, pp. 3788\u20133805 PMLR"},{"key":"1083_CR38","unstructured":"Puthiya\u00a0Parambath SA, Al-Fahad SAM, Anagnostopoulos C, Kolomvatsos K (2024) Sequential block elimination for dynamic pricing"},{"key":"1083_CR39","unstructured":"Russo D (2016) Simple bayesian algorithms for best arm identification. In: Conference on Learning Theory, pp. 1417\u20131418. PMLR"},{"key":"1083_CR40","unstructured":"Sebastian\u00a0Stein RM-S (2023) Interactive Model-based Probabilistic Visualisations for Exploring Decisions. Technical report, University of Glasgow, School Of Compting Science (2023)"},{"issue":"16","key":"1083_CR41","doi-asserted-by":"publisher","first-page":"4281","DOI":"10.1109\/TSP.2017.2706192","volume":"65","author":"S Shahrampour","year":"2017","unstructured":"Shahrampour S, Noshad M, Tarokh V (2017) On sequential elimination algorithms for best-arm identification in multi-armed bandits. IEEE Trans Signal Process 65(16):4281\u20134292","journal-title":"IEEE Trans Signal Process"},{"key":"1083_CR42","unstructured":"Sutton RS, Barto AG (2018) Reinforcement Learning: An Introduction. MIT press"},{"key":"1083_CR43","first-page":"18586","volume":"35","author":"A Tirinzoni","year":"2022","unstructured":"Tirinzoni A, Degenne R (2022) On elimination strategies for bandit fixed-confidence identification. Adv Neural Inf Process Syst 35:18586\u201318598","journal-title":"Adv Neural Inf Process Syst"},{"key":"1083_CR44","unstructured":"Wang S, Zhu J (2022) Thompson sampling for (combinatorial) pure exploration. In: International Conference on Machine Learning, pp. 23470\u201323483. PMLR"},{"key":"1083_CR45","unstructured":"Xu J, Wang Y-X (2022) Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise. In: International Conference on Artificial Intelligence and Statistics, pp. 9643\u20139662. PMLR"},{"key":"1083_CR46","unstructured":"Zhuang H, Wang C, Wang Y (2017) Identifying outlier arms in multi-armed bandit. Adv Neural Inf Process Syst 30"},{"key":"1083_CR47","unstructured":"Zhu Y, Katariya S, Nowak R (2020) Robust outlier arm identification. In: International Conference on Machine Learning, pp. 11566\u201311575. PMLR"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-024-01083-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-024-01083-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-024-01083-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T11:46:16Z","timestamp":1737027976000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-024-01083-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,18]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["1083"],"URL":"https:\/\/doi.org\/10.1007\/s10618-024-01083-2","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"type":"print","value":"1384-5810"},{"type":"electronic","value":"1573-756X"}],"subject":[],"published":{"date-parts":[[2024,12,18]]},"assertion":[{"value":"7 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"7"}}