# How do find the best arm in a multi-armed bandit when exploitation is unimportant?

I have a problem similar to the 'Bernoulli bandit' problem in the exploration-exploitation paradigm, but without the exploitation element.

In particular, I have many levers that I can pull and each pull either succeeds or fails a proportion of the time that is fixed but unknown, and different for each lever. I want to find the lever that succeeds the most often. What's a good strategy to use if I want to minimise the expected number of pulls until I'm 99% sure I've found the one with the highest proportion of successes?

This differs from the usual multi-armed bandit problem in that during this testing I'm not rewarded for getting successes rather than failures. So I don't particularly favour strategies which get more successes. In particular I tried Thompson Sampling and I found that once it had found a good lever it spent too much time pulling that lever and not enough time trying to rule out the second best possibilities.

What would be a good algorithm for this problem? Can we say what would be optimal from a Bayesian perspective?

• You say that you want to find "the right one." Which lever is "the right one"? The one with the highest proportion of rewards? Or something else? I'm asking because you've said that you don't get rewards for successes, so it's not totally clear what the ultimate objective is.
– Sycorax
Jun 22, 2022 at 16:11
• @Sycorax Yes, the one which succeeds the most often. I've improved the wording, thanks! The context is that I want to find the optimal strategy in a game. I'm simulating the game to test various strategies, but I don't actually care about winning the simulations. Jun 22, 2022 at 16:20
• Thanks for doing that. I've edited your title because I think the new one is a better summary. Feel free to change it, but keep in mind that (1) it should be a question and (2) should summarize the key think you want to know about.
– Sycorax
Jun 22, 2022 at 16:24

If you are interested in minimizing the number of pulls to identify the best arm, the setting you want to use is 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. An algorithm $$\mathcal{A}$$ is optimal in the sense that no other algorithm can do better than $$\mathcal{A}$$ on a specific set of problems (e.g. with stochastic Gaussian or Bernoulli reward distributions).