Best Arm Identification in Spectral Bandits

• URL: http://arxiv.org/abs/2005.09841v1
• Date: Wed, 20 May 2020 04:12:04 GMT
• Title: Best Arm Identification in Spectral Bandits
• Authors: Tom\'a\v{s} Koc\'ak, Aur\'elien Garivier
• Abstract summary: Best Arm Identification (BAI) is an important challenge in many applications ranging from parameter tuning to clinical trials. We study best-arm identification with fixed confidence in bandit models with graph smoothness constraint.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study best-arm identification with fixed confidence in bandit models with graph smoothness constraint. We provide and analyze an efficient gradient ascent algorithm to compute the sample complexity of this problem as a solution of a non-smooth max-min problem (providing in passing a simplified analysis for the unconstrained case). Building on this algorithm, we propose an asymptotically optimal strategy. We furthermore illustrate by numerical experiments both the strategy's efficiency and the impact of the smoothness constraint on the sample complexity. Best Arm Identification (BAI) is an important challenge in many applications ranging from parameter tuning to clinical trials. It is now very well understood in vanilla bandit models, but real-world problems typically involve some dependency between arms that requires more involved models. Assuming a graph structure on the arms is an elegant practical way to encompass this phenomenon, but this had been done so far only for regret minimization. Addressing BAI with graph constraints involves delicate optimization problems for which the present paper offers a solution.

Related papers

Err

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.