{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T00:14:55Z","timestamp":1758672895948,"version":"3.44.0"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:p>This paper studies lexicographic multi-armed bandits (MAB), where after selecting an arm, the agent observes a reward vector including multiple objectives, each with a different level of importance. Although previous literature has proposed the algorithm for lexicographic MAB, their algorithm suffers from several limitations: (1) it exhibits poor adversarial robustness due to its reliance on stochastic rewards, (2) its regret bound is suboptimal compared to single-objective counterparts, and (3) the regret bound does not adapt to specific problem instances. To address these limitations, we study lexicographic MAB with adversarial corruptions, where an adversary might corrupt the stochastic rewards with a corruption budget of C. First, when the value of C is known, we propose an algorithm achieving a problem-dependent regret bound of O(\u2211(log T \/ \u0394\u2071(a) + C)) for the i-th objective (i \u2208 [M]), where \u0394\u2071(a) is the reward gap for arm a on the i-th objective, and M is the number of objectives. In the purely stochastic setting (C=0), this regret bound approaches optimality. Second, we introduce another algorithm that does not require value of C but incurs a less favorable regret bound of O(\u2211(\u03b3_T \/ \u0394\u2071(a) + \u03b3_T)) for the i-th objective, where \u03b3_T = O((log T)\u00b2 + KC(log T)\u00b2). Finally, we conduct experiments on both synthetic and real-world datasets to verify the effectiveness of our algorithms.<\/jats:p>","DOI":"10.24963\/ijcai.2025\/754","type":"proceedings-article","created":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:10:40Z","timestamp":1758269440000},"page":"6776-6784","source":"Crossref","is-referenced-by-count":0,"title":["Problem-dependent Regret for Lexicographic Multi-Armed Bandits with Adversarial Corruptions"],"prefix":"10.24963","author":[{"given":"Bo","family":"Xue","sequence":"first","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Hong Kong, China"},{"name":"The City University of Hong Kong Shenzhen Research Institute, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xi","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Hong Kong, China"},{"name":"The City University of Hong Kong Shenzhen Research Institute, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuanyu","family":"Wan","sequence":"additional","affiliation":[{"name":"School of Software Technology, Zhejiang University, Ningbo, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qingfu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Hong Kong, China"},{"name":"The City University of Hong Kong Shenzhen Research Institute, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"34","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2025","name":"Thirty-Fourth International Joint Conference on Artificial Intelligence {IJCAI-25}","start":{"date-parts":[[2025,8,16]]},"theme":"Artificial Intelligence","location":"Montreal, Canada","end":{"date-parts":[[2025,8,22]]}},"container-title":["Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T11:35:03Z","timestamp":1758627303000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2025\/754"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2025,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2025\/754","relation":{},"subject":[],"published":{"date-parts":[[2025,9]]}}}