On the Hardness of Bandit Learning

Nataly Brukhim, Aldo Pacchiano, Miroslav Dudik +1

We study the task of bandit learning, also known as best-arm identification, under the assumption that the true reward function f belongs to a known, but arbitrary, function class…