4
$\begingroup$

Multi-armed_bandit problem defenition from Wikipeda:

"In probability theory, the multi-armed bandit problem (sometimes called the K-[1] or N-armed bandit problem) is the problem a gambler faces at a row of slot machines, sometimes known as "one-armed bandits", when deciding which machines to play, how many times to play each machine and in which order to play them. When played, each machine provides a random reward from a distribution specific to that machine. The objective of the gambler is to maximize the sum of rewards earned through a sequence of lever pulls" (http://en.wikipedia.org/wiki/Multi-armed_bandit)

In other words Multi-armed bandit (MAB) problems are a class of sequential resource allocation problems concerned with allocating one or more resources among several alternative (competing) projects / 'arms'. Such problems have a conflict between making decisions (allocating resources) that yield high current rewards, versus making decisions that sacrifice current gains with the prospect of better future rewards.

Any Java implementations for these algorithms?

$\endgroup$
  • $\begingroup$ Most certainly. What is your goal? $\endgroup$ – ziggystar Apr 11 '13 at 11:31
  • $\begingroup$ The goal is to learn MAB using Feynman's problem as a toy task: feynmanlectures.info/solutions/restaurant_problem_sol_1.html $\endgroup$ – Anton Ashanin Apr 11 '13 at 12:08
  • $\begingroup$ If you want to learn, why not code it yourself? $\endgroup$ – ziggystar Apr 11 '13 at 12:30
  • $\begingroup$ Other people code helps me to understand how the algorithm works. Do you have any examples of MAB in Java or Python, maybe? $\endgroup$ – Anton Ashanin Apr 11 '13 at 13:03
  • $\begingroup$ This is probably what you are looking for: mloss.org/software/view/415 $\endgroup$ – BigG Jan 28 '14 at 18:50
3
$\begingroup$

You're only describing a problem. There are many different algorithms that can be applied to solve it, see e.g. http://lane.compbio.cmu.edu/courses/slides_ucb.pdf.

The UCB1 algorithm is so dead simple, reading Java code to understand how it works is probably a bad idea - unless you want to learn Java:

Play machine $j$, that maximizes

$$\bar{x}_j+\sqrt{\frac{2\ln n}{n_j}},$$ where $\bar{x}_j$ is the average reward obtained from machine $j$, $n_j$ is how often $j$ has been played and $n$ is the number of total plays. The 2 in the formula is a constant which can be changed to tune the exploration vs exploitation of the algorithm (higher number results in more exploration).

$\endgroup$
  • $\begingroup$ By any chance might you have the pdf you are referring to and could share it? The page doesn't seem to be working. References to other material for beginners would also be welcomed. Thanks $\endgroup$ – Andrea Barraza Feb 22 '17 at 15:39

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.