Thresholding Bandit for Dose-ranging: The Impact of Monotonicity

Aurélien Garivier (1) , Pierre Ménard (1) , Laurent Rossi (1) , Pierre Ménard (1)

1 IMT - Institut de Mathématiques de Toulouse UMR5219

We analyze the sample complexity of the thresholding bandit problem, with and without the assumption that the mean values of the arms are increasing. In each case, we provide a lower bound valid for any risk δ and any δ-correct algorithm; in addition, we propose an algorithm whose sample complexity is of the same order of magnitude for small risks. This work is motivated by phase 1 clinical trials, a practically important setting where the arm means are increasing by nature, and where no satisfactory solution is available so far.

Mots clés: thresholding bandits; multi-armed bandits; best arm identification; Unimodal regression; uni- modal regression; isotonic regression

Domaines: Statistiques [math.ST]; Machine Learning [stat.ML]; Théorie [stat.TH]

Aurélien Garivier, Pierre Ménard, Laurent Rossi, Pierre Ménard. Thresholding Bandit for Dose-ranging: The Impact of Monotonicity. 2018. ⟨hal-01629479v2⟩