5
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Sycorax
    Jun 22, 2022 at 16:11
  • $\begingroup$ @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. $\endgroup$ Jun 22, 2022 at 16:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sycorax
    Jun 22, 2022 at 16:24

1 Answer 1

4
$\begingroup$

This answer is relevant to your question.

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).

There are plenty of other algorithms in the BAI literature (see Audibert et al. or Jamieson et al.). Thompson Sampling can also work optimally in Best Arm identification but you need to tweak the algorithm a bit and choose carefully the prior and update the posterior properly. This paper is a good reference for the pure exploration problem in Bayesian setting.

To find more algorithms you can just google "Best Arm Identification" or "Pure Exploration".

$\endgroup$

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.