4 ms·

The article doesn't do a very good job of explaining "Bandit algorithms". The closest s/he comes is this, but that really doesn't enlighten me: So, what is the

by ojilles 15y ago

The article doesn't do a very good job of explaining "Bandit algorithms". The closest s/he comes is this, but that really doesn't enlighten me: So, what is the bandit problem? You have a set of choices you can make. On the web these could be different images to display, or different wordings for a button, and so on. Each time you make a choice you get a reward. For example, you might get a reward of 1 if a button is clicked, and reward of 0 otherwise. Your goal is to maximise your total reward over time. This clearly fits the content optimisation problem. Edit: Anyone have better pointers? (Other than the UU article referenced in the post)

noelwelsh 15y ago
There are a bunch of papers I can point you to. Is that what you're looking for?
- smu 15y ago
  I would like that.
  - noelwelsh 15y ago
    Check out "Prediction Learning and Games" for a fairly recent introduction to the fundamental. See the work by Daniel Hsu, John Langford, and Jean-Yves Audibert (to name a few of the more prominent researchers) for interesting recent work. If you want more detail drop me a line.
  - MLnick 15y ago
    +1 for Langford. He and many others (e.g. Deepak Agarwal) at Y! are among the most prolific publishers on this topic. Check out: http://hunch.net/~exploration_learning/ http://hunch.net/~exploration_learning/ for a good, but pretty technical overview.
charliepark 15y ago
I could be misreading it, but I believe the premise is "more traction => more action". If I'm right, the idea is that the algorithm dynamically weights the "display frequency" of the two (or n) options. So as one of the a/b options shows itself to be more successful, it's shown more frequently. Because the test is self-correcting, you as an A/B test runner don't have to decide when the results are significant enough, and the program itself will automatically choose the more successful option.
- noelwelsh 15y ago
  That's correct.
- datadon 15y ago
  Going purely off of your boiled down description, this seems like a more advanced version of Genetify (https://github.com/gregdingle/genetify/wiki https://github.com/gregdingle/genetify/wiki). @noelwelsh - care to comment on now what you're doing at Untyped differs from what Genetify offers?
  - StavrosK 15y ago
    That looks like it uses genetic algorithms, which is much less optimal and more exploratory than bandit algorithms. What noelwelsh is proposing would lead to better results much more quickly and without random permutations of elements.
    - noelwelsh 15y ago
      I agree :)
  - e-dard 15y ago
    The difference in performance between using evolutionary approaches and bandit algorithms is complex and problem dependent. There is no "one algorithm is better than the other". I've used both approaches for a different application and neither dominate the other.
StavrosK 15y ago
The original formulation of the problem is that you have a slot machine (one-armed bandit) with multiple arms, each arm having different payoffs. You want to maximise payoff while minimizing time spent on arms that don't pay off as well, but you obviously need to spend enough money on everything to estimate the probabilities. That's the gist of the problem.
rakkhi 15y ago
Agreed. So what I love about the A/B test is how simple it is to explain and run. How do I run a bandit test? Is it effectively what Google is doing when you tick the adwords option display successful ad's more often? Is there a simple article that explains how to run a bandit test on exactly the example provided by the OP: which button text (e.g. click here, buy now) should I use to get maximum number of conversions?
tel 15y ago
The gist (from reading the paper) is to compute a ranking of the choices based on past performance that optimally selects the best bandit based on incomplete (and stochastic) observations. I can understand some hesitance to post the exact algorithm because, like anything that fixes the large number of heinous flaws in basic hypothesis testing, it gets complicated. Worse, the paper presents a number of algorithms which appear, at first glance, to be very simple and performant. The primary problem with that is they are analyzing a very simplified version of the problem; assuming independence greatly reduces the practical flexibility of the algorithm. Anyway, the basic flavor of the algorithm is to try to spend most of your time running the choice with the highest average reward (click-throughs, dollars) with some deterministic or stochastic correction for the chance that a worse performing model just happened to have the highest average at this point in your test.
fhars 15y ago
Here is another paper that looks promising: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.4518 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.... 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. The problem is: should he continue to pull the arm that has given the best payout until now, or try another arm he doesn't yet know much about to see if it has a higher payout?

by ojilles 15y ago

noelwelsh 15y ago

There are a bunch of papers I can point you to. Is that what you're looking for?

smu 15y ago
I would like that.
- noelwelsh 15y ago
  Check out "Prediction Learning and Games" for a fairly recent introduction to the fundamental. See the work by Daniel Hsu, John Langford, and Jean-Yves Audibert (to name a few of the more prominent researchers) for interesting recent work. If you want more detail drop me a line.
- MLnick 15y ago
  +1 for Langford. He and many others (e.g. Deepak Agarwal) at Y! are among the most prolific publishers on this topic. Check out: http://hunch.net/~exploration_learning/ http://hunch.net/~exploration_learning/ for a good, but pretty technical overview.

charliepark 15y ago

I could be misreading it, but I believe the premise is "more traction => more action". If I'm right, the idea is that the algorithm dynamically weights the "display frequency" of the two (or n) options. So as one of the a/b options shows itself to be more successful, it's shown more frequently. Because the test is self-correcting, you as an A/B test runner don't have to decide when the results are significant enough, and the program itself will automatically choose the more successful option.

noelwelsh 15y ago
That's correct.
datadon 15y ago
Going purely off of your boiled down description, this seems like a more advanced version of Genetify (https://github.com/gregdingle/genetify/wiki https://github.com/gregdingle/genetify/wiki). @noelwelsh - care to comment on now what you're doing at Untyped differs from what Genetify offers?
- StavrosK 15y ago
  That looks like it uses genetic algorithms, which is much less optimal and more exploratory than bandit algorithms. What noelwelsh is proposing would lead to better results much more quickly and without random permutations of elements.
  - noelwelsh 15y ago
    I agree :)
- e-dard 15y ago
  The difference in performance between using evolutionary approaches and bandit algorithms is complex and problem dependent. There is no "one algorithm is better than the other". I've used both approaches for a different application and neither dominate the other.

StavrosK 15y ago

The original formulation of the problem is that you have a slot machine (one-armed bandit) with multiple arms, each arm having different payoffs. You want to maximise payoff while minimizing time spent on arms that don't pay off as well, but you obviously need to spend enough money on everything to estimate the probabilities. That's the gist of the problem.

rakkhi 15y ago

Agreed. So what I love about the A/B test is how simple it is to explain and run. How do I run a bandit test? Is it effectively what Google is doing when you tick the adwords option display successful ad's more often? Is there a simple article that explains how to run a bandit test on exactly the example provided by the OP: which button text (e.g. click here, buy now) should I use to get maximum number of conversions?

tel 15y ago

The gist (from reading the paper) is to compute a ranking of the choices based on past performance that optimally selects the best bandit based on incomplete (and stochastic) observations. I can understand some hesitance to post the exact algorithm because, like anything that fixes the large number of heinous flaws in basic hypothesis testing, it gets complicated. Worse, the paper presents a number of algorithms which appear, at first glance, to be very simple and performant. The primary problem with that is they are analyzing a very simplified version of the problem; assuming independence greatly reduces the practical flexibility of the algorithm. Anyway, the basic flavor of the algorithm is to try to spend most of your time running the choice with the highest average reward (click-throughs, dollars) with some deterministic or stochastic correction for the chance that a worse performing model just happened to have the highest average at this point in your test.

fhars 15y ago

Here is another paper that looks promising: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.4518 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.... 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. The problem is: should he continue to pull the arm that has given the best payout until now, or try another arm he doesn't yet know much about to see if it has a higher payout?