I've read about a number of algorithms for solving n-armed bandit problems like $\epsilon$-greedy, softmax, and UCB1, but I'm having some trouble sorting through what approach is best for minimizing regret.

Is there a known optimal algorithm for solving the n-armed bandit problem? Is there a choice of algorithm that seems to perform best in practice?

  • $\begingroup$ Presumably there is not a recognised optimal solution, as otherwise the Wikipedia page would say so and there would not be an experimental Sourceforge page $\endgroup$
    – Henry
    Commented May 11, 2011 at 20:17
  • $\begingroup$ Shouldn't this be on Theoretical Computer Science SE? $\endgroup$
    – user88
    Commented May 12, 2011 at 6:31
  • 1
    $\begingroup$ @mbq since reinforcement learning is a branch of machine learning, I don't think so ;) $\endgroup$
    – steffen
    Commented May 12, 2011 at 14:18
  • $\begingroup$ @steffen Sure, the name seemed "tcsy". $\endgroup$
    – user88
    Commented May 12, 2011 at 14:48
  • $\begingroup$ @mbq I don't get it. What does "tscy" mean ? $\endgroup$
    – steffen
    Commented May 13, 2011 at 8:28

1 Answer 1


Here are two survey papers I have found recently. I have not read them yet, but the abstracts sound promising.

Joann`s Vermorel and Mehryar Mohri: Multi-Armed Bandit Algorithms and Empirical Evaluation (2005)

From the abstract:

The multi-armed bandit problem for a gambler is to decide which arm of a K-slot machine to pull to maximize his total reward in a series of trials. Many real-world learning and optimization problems can be modeled in this way. Several strategies or algorithms have been proposed as a solution to this problem in the last two decades, but, to our knowledge, there has been no common evaluation of these algorithms.

Volodymyr Kuleshov and Doina Precup: Algorithms for the multi-armed bandit problem (2000) From the abstract:

Secondly, the performance of most algorithms varies dramatically with the parameters of the bandit problem. Our study identifies for each algorithm the settings where it performs well, and the settings where it performs poorly.


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.