We study the stochastic multi-armed bandit problem when one knows the value @math of an optimal arm, as a well as a positive lower bound on the smallest positive gap @math . We propose a new randomized policy that attains a regret uniformly bounded over time in this setting. We also prove several lower bounds, which show in particular that bounded regret is not possible if one only knows @math , and bounded regret of order @math is not possible if one only knows @math
The knowledge of @math was also exploited in other works. For instance in @cite_12 , the authors showed that knowing @math allows for policies with provably better concentration properties. Their policies are based on sequential likelihood ratio tests for @math vs. @math (assuming Gaussian distributions to compute the likelihoods). To some extent it was to be expected that the knowledge of @math leads to an improved regret as it partially removes the need for exploration: if one arm has empirical performances close to @math , one can be confident that this is the best arm without worrying that it could be the best arm only because we have not yet explored enough the other options. However note that the problem turns out to be more subtle than the above simple argument and underlines the fact that one needs more than the knowledge of @math in order to have a bounded regret with optimal scaling in @math . Indeed, Theorem implies that the sole knowledge of @math does not warrant the bounded property for the rescaled regret @math .
@cite_12
2167875775
This paper studies the deviations of the regret in a stochastic multi-armed bandit problem.When the total number of plays n is known beforehand by the agent, (2009) exhibit a policy such that with probability at least 1-1 n, the regret of the policy is of order log n. They have also shown that such a property is not shared by the popular ucb1 policy of (2002). This work first answers an open question: it extends this negative result to any anytime policy. The second contribution of this paper is to design anytime robust policies for specific multi-armed bandit problems in which some restrictions are put on the set of possible distributions of the different arms.