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
    May 11 '11 at 20:17
  • $\begingroup$ Shouldn't this be on Theoretical Computer Science SE? $\endgroup$
    – user88
    May 12 '11 at 6:31
  • 1
    $\begingroup$ @mbq since reinforcement learning is a branch of machine learning, I don't think so ;) $\endgroup$
    – mlwida
    May 12 '11 at 14:18
  • $\begingroup$ @steffen Sure, the name seemed "tcsy". $\endgroup$
    – user88
    May 12 '11 at 14:48
  • $\begingroup$ @mbq I don't get it. What does "tscy" mean ? $\endgroup$
    – mlwida
    May 13 '11 at 8:28

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, privacy policy and cookie policy

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