{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:43:31Z","timestamp":1723016611551},"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":[[2021,8]]},"abstract":"<jats:p>We propose an analysis of Probably Approximately Correct (PAC) identification of an \u03f5-best arm in graph bandit models with Gaussian distributions. We consider finite but potentially very large bandit models where the set of arms is endowed with a graph structure, and we assume that the arms' expectations \u03bc are smooth with respect to this graph. Our goal is to identify an arm whose expectation is at most \u03f5 below the largest of all means. We focus on the fixed-confidence setting: given a risk parameter \u03b4, we consider sequential strategies that yield an \u03f5-optimal arm with probability at least 1-\u03b4. All such strategies use at least T*(\u03bc)log(1\/\u03b4) samples, where R is the smoothness parameter. We identify the complexity term  T*(\u03bc) as the solution of a min-max problem for which we give a game-theoretic analysis and an approximation procedure. This procedure is the key element required by the asymptotically optimal Track-and-Stop strategy.<\/jats:p>","DOI":"10.24963\/ijcai.2021\/363","type":"proceedings-article","created":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T11:00:49Z","timestamp":1628679649000},"page":"2636-2642","source":"Crossref","is-referenced-by-count":0,"title":["Epsilon Best Arm Identification in Spectral Bandits"],"prefix":"10.24963","author":[{"given":"Tom\u00e1\u0161","family":"Koc\u00e1k","sequence":"first","affiliation":[{"name":"Unit\u00e9 de Math\u00e9matiques Pures et Appliqu\u00e9es et Laboratoire de l'Informatique du Parall\u00e9lisme \u00c9cole Normale Sup\u00e9rieure de Lyon, Universit\u00e9 de Lyon"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aur\u00e9lien","family":"Garivier","sequence":"additional","affiliation":[{"name":"Unit\u00e9 de Math\u00e9matiques Pures et Appliqu\u00e9es et Laboratoire de l'Informatique du Parall\u00e9lisme \u00c9cole Normale Sup\u00e9rieure de Lyon, Universit\u00e9 de Lyon"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"30","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2021","name":"Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}","start":{"date-parts":[[2021,8,19]]},"theme":"Artificial Intelligence","location":"Montreal, Canada","end":{"date-parts":[[2021,8,27]]}},"container-title":["Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T11:02:51Z","timestamp":1628679771000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2021\/363"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2021,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2021\/363","relation":{},"subject":[],"published":{"date-parts":[[2021,8]]}}}