{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T03:02:15Z","timestamp":1773802935668,"version":"3.50.1"},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"24","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAAI"],"abstract":"<jats:p>Best arm identification (BAI) aims to identify the highest-\nperformance arm among a set of K arms by collecting\nstochastic samples from each arm. In real-world problems,\nthe best arm needs to satisfy additional feasibility constraints.\nWhile there is limited prior work on BAI with feasibility\nconstraints, they typically assume the performance and con-\nstraints are observed simultaneously on each pull of an arm.\nHowever, this assumption does not reflect most practical use\ncases, e.g., in drug discovery, we wish to find the most potent\ndrug whose toxicity and solubility are below certain safety\nthresholds. These safety experiments can be conducted separately from the potency measurement. Thus, this requires de-\nsigning BAI algorithms that not only decide which arm to pull\nbut also decide whether to test for the arm\u2019s performance or\nfeasibility. In this work, we study feasible BAI which allows\na decision-maker to choose a tuple (i, \u2113), where i \u2208 [K] de-\nnotes an arm and \u2113 denotes whether she wishes to test for its\nperformance (\u2113 = 0) or any of its N feasibility constraints\n(\u2113 \u2208 [N ]). We focus on the fixed confidence setting, which\nis to identify the feasible arm with the highest performance,\nwith a probability of at least 1 \u2212 \u03b4. We propose an efficient\nalgorithm and upper-bound its sample complexity, showing\nour algorithm can naturally adapt to the problem\u2019s difficulty\nand eliminate arms by worse performance or infeasibility,\nwhichever is easier. We complement this upper bound with\na lower bound showing that our algorithm is asymptotically\n(\u03b4 \u2192 0) optimal. Finally, we empirically show that our algorithm outperforms other state-of-the-art BAI algorithms in\nboth synthetic and real-world datasets.<\/jats:p>","DOI":"10.1609\/aaai.v40i24.39063","type":"journal-article","created":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:10:53Z","timestamp":1773796253000},"page":"19808-19816","source":"Crossref","is-referenced-by-count":0,"title":["Constrained Best Arm Identification with Tests for Feasibility"],"prefix":"10.1609","volume":"40","author":[{"given":"Ting","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kirthevasan","family":"Kandasamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9382","published-online":{"date-parts":[[2026,3,14]]},"container-title":["Proceedings of the AAAI Conference on Artificial Intelligence"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/39063\/43025","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/39063\/43025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:10:53Z","timestamp":1773796253000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/39063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,14]]},"references-count":0,"journal-issue":{"issue":"24","published-online":{"date-parts":[[2026,3,17]]}},"URL":"https:\/\/doi.org\/10.1609\/aaai.v40i24.39063","relation":{},"ISSN":["2374-3468","2159-5399"],"issn-type":[{"value":"2374-3468","type":"electronic"},{"value":"2159-5399","type":"print"}],"subject":[],"published":{"date-parts":[[2026,3,14]]}}}