I'm wondering if there's an algorithm that minimizes the expected posterior loss for the best performing bandit where regret is calculated as the number of trials to achieve a threshold for posterior loss.

Example: Let's say we run an AB test to compare click rates for 3 different creatives. For each user, we can decide which creative she will get. Since we are just pretending this is a real-world scenario, we don't gain anything from the click - but we have to pay for each impression the same. Is there a way (an algorithm) to find which creative performs the best in the least amount of impression (trials)?


1 Answer 1


The setting you are looking for is named Best Arm Identification. In this setting, you have no notion of regret but you just aim at identifying the best arm as fast as possible (say in $\tau$ steps) and with a probability at least equal to $1-\delta$, for $\delta\in(0,1)$.

There are many algorithms that have been proposed to solve this problem. A provably (asymptotically for $\delta \to 0$) optimal algorithm is proposed by Garivier and Kaufmann, but there are plenty of other algorithms (see Audibert et al. or Jamieson et al.).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.