Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

chrisstucchio.com

Post reply on HN
Print view View original

41–50 of 56 posts

Re: Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

#41

Post by yummyfajitas »

btilly wrote: post #36
noelwelsh wrote: post #4

Let's settle this with science rather than rhetoric. I'd like to do some proper comparisons between bandit algorithms and A/B testing. Unfortunately we haven't been saving time series data at Myna, so we don't have any test data. If anyone has time series data from an A/B test, and is happy to donate it to the cause, please get in touch (email in profile). Updated for clarity.

Unfortunately most of the A/B tests that I am involved with at the moment simply do not look anything like what you'd want for a traditional bandit approach. For a start the data is fundamentally 2-dimensional. I am testing by user, and users may take days to hit a conversion metric. Furthermore a large chunk of the population has to go in the test before I get any data at all about how any of them will perform. This…

Actually you are correct that in situations with latency (i.e., you have the opportunity to play a machine at t=0, another opportunity to play at t=1, but you don't receive results of the plays until t=10), UCBx doesn't work.

It's not even a question of statistical power, it's just a matter of typing. Typical bandit algorithms use the function play_machine: Machine -> Float. In the situation you describe, the type signature is Machine -> Future[Float].

I'm working on a modified version which handles those situations, however. It's along the lines of UCB2, tweaking the formula so that the numerator is proportional to the number of plays you've submitted while the denominator is the number of plays you've received. Once I finish the math I'll write it up.

Re: Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

#42

Post by yummyfajitas »

patio11 wrote: post #22
yummyfajitas wrote: post #21

Earlier quoted context omitted.

Pick A/B testing, bandit testing, whatever -- any option in the set, even with poor algorithms and/or the easiest errors I can think of, strictly dominate not testing at all. So I submitted this post and went off to boxing. On the train ride back, I thought "I hope I don't make people think they shouldn't A/B test. And at the same time you were writing this post, I added a conclusion to my blog post saying the same t…

Unless I misunderstand bandit algorithms, there's a trivial modification that makes the actual, practical administration of them essentially identical to A/B testing with regards to when you can rip out code. If A smashes B, then bandit will converge in a very obvious manner on A, and you pick it and delete the B code branch, accepting future regret from the possibility that B was in fact better as a cost of doing bu…

You are correct for practical purposes.

However, you are mathematically wrong. Doing things the way you describe is another form of A/B testing, just one designed to reduce the regret incurred during the test. You still get the linear growth in regret I described (i.e., there is some % chance you picked the wrong branch, and you are leaving money on the table forever after).

Of course, your way is also economically correct, and the theoretical CS guys are wrong. They shouldn't be trying to minimize regret, they should be minimizing time discounted regret.

(Yes, I'm being extremely pedantic. I'm a mathematician, it comes with the territory.)

Re: Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

#43

Post by greendestiny »

yummyfajitas wrote: post #42
patio11 wrote: post #22

Earlier quoted context omitted.

Unless I misunderstand bandit algorithms, there's a trivial modification that makes the actual, practical administration of them essentially identical to A/B testing with regards to when you can rip out code. If A smashes B, then bandit will converge in a very obvious manner on A, and you pick it and delete the B code branch, accepting future regret from the possibility that B was in fact better as a cost of doing bu…

You are correct for practical purposes. However, you are mathematically wrong. Doing things the way you describe is another form of A/B testing, just one designed to reduce the regret incurred during the test. You still get the linear growth in regret I described (i.e., there is some % chance you picked the wrong branch, and you are leaving money on the table forever after). Of course, your way is also economically c…

Well fundamentally website optimization is not a multi-armed bandit problem. You are not simply choosing between machines. Instead each website change is another node on a tree and you want to find the highest performing path in constantly changing world, with additional constraints that you can't keep incompatible machines for very long.

A guess at good strategy in those situations would be something that enables you to choose a good path from a small number of options and keep doing so - on the basis that the cumulative advantage will be far more important than any particular choice in itself. Sounds like A/B testing would win if you could actually map the complexity of the problem correctly.

Re: Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

#44

Post by polyfractal »

btilly wrote: post #29
blueskittle wrote: post #25

As someone who works for a major e-commerce site, I am often the one who has the most influence when it comes time to decide which testing method to adopt. Multi-armed Bandit testing can be good, just as standard A/B testing can be good. But the factor which trumps all of these are the total costs of testing (and the return on investment to the business). One must consider the following before undertaking any of thes…

If you've conducted multiple tests and "time to implement the testing code" is a major consideration, then you're doing it wrong. If ROI is also a major consideration, then again you're doing it wrong. Seriously to add an email test right now at the company I'm contracting for takes 2 lines of code. One appears in the program that sends email and looks like: $email_state_contact->ab_test_version("test_1234", {A => 1,…

I can imagine a number of situations where the implementation is significantly more complex. While ideally A/B tests should be looking at relatively small changes, where each change is independent, many times people are making profoundly larger changes.

If you are testing the conversion rate in shopping carts, and the changes involves drastic redesigns of the flow through the shopping cart process, that could be a serious technological difference and requires substantial time to implement.

Not every test is as easy as changing the copy on an email.

Re: Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

#45

Post by btilly »

polyfractal wrote: post #44
btilly wrote: post #29

Earlier quoted context omitted.

If you've conducted multiple tests and "time to implement the testing code" is a major consideration, then you're doing it wrong. If ROI is also a major consideration, then again you're doing it wrong. Seriously to add an email test right now at the company I'm contracting for takes 2 lines of code. One appears in the program that sends email and looks like: $email_state_contact->ab_test_version("test_1234", {A => 1,…

I can imagine a number of situations where the implementation is significantly more complex. While ideally A/B tests should be looking at relatively small changes, where each change is independent, many times people are making profoundly larger changes. If you are testing the conversion rate in shopping carts, and the changes involves drastic redesigns of the flow through the shopping cart process, that could be a se…

Even if you're making larger and more complex changes, the overhead of your testing methodology remains the same. That is how you measure things should be a fixed (small) effort, The cost of building the test is whatever the test is.

In other words multi-armed bandit versus A/B test is something that you shouldn't be deciding based on the effort of the testing methodology.

Re: Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

#46

Post by conductrics »

Disclaimer: I also have software for running AB/MVT as well as adaptive control problems (so bandits as well as extended sequential decisions) at www.conductrics.com.

I wouldn't sweat too much UCB methods vs e-greedy or other heuristics for balancing explore/exploit. E-greedy (and e-greedy decreasing) is nice because it is simple. Softmax/Boltzman, is interesting since it is satisfying in that it selects arms weighted by the estimated means, and UCB-Tuned and UCB-Normal are nice because, like AB testing, they take variance measures directly into account when selecting an arm. Take a look at this paper from Doina Precup (who is super nice BTW) and Volodymyr Kuleshov from 2000 http://www.cs.mcgill.ca/~vkules/bandits.pdf they have comparisons between various methods. Guess what - the simple methods work just fine. Of course there are various Bayesion versions - esp of UCB. Nando de Freitas over at UBC has a recent ICML paper on using the Gaussian Process for Bandits (based on a form of UCB). See http://www.cs.ubc.ca/~nando/papers/BayesBandits.pdf I have not given it a tight read, but not sure what the practical return would be. Plus you have to fiddle with picking a Kernel function, and I imagine length scales and the rest of hyper parameters associated with GPs. I did read a working paper from Nando a few years back that used a random forest as a prior - I can't seem to find it now. BTW - John Langford is program chair of this year’s ICML over in Edinburgh. If you are in the UK might be worth it to pop up and attend. Plus Chris Williams is there at Edinburgh, so maybe you can corner him about GPs. Although he has moved on from GPs - he still wrote (well, co-wrote) the book and is one of the smartest people I have ever met.

Re: Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

#47

Post by patio11 »

lucisferre wrote: post #38
yummyfajitas wrote: post #21

Earlier quoted context omitted.

Pick A/B testing, bandit testing, whatever -- any option in the set, even with poor algorithms and/or the easiest errors I can think of, strictly dominate not testing at all. So I submitted this post and went off to boxing. On the train ride back, I thought "I hope I don't make people think they shouldn't A/B test. And at the same time you were writing this post, I added a conclusion to my blog post saying the same t…

Wouldn't bad A/B testing be a 50/50 solution. Is making decisions on data without statistical significance any better than throwing darts blind?

Consider the bad A/B testing algorithm implemented by Dr. Awesome. Instead of reporting statistical significance, if it would be statistically significant below 10% chance of coincidence, he reliably reports "It was Awesome!" Dr. Awesome then promptly burns his notes to warm his awesome heart.

Even though many people would take issue with using 10% (a lot of practitioners like 5%) and Dr. Awesome has some serious issues with data retention policies, if you always follow Dr. Awesome's advice, you'll win 9 times for every time you lose. I'll take those odds.

Say Dr. Awesome also has one additional problem: one time of twenty, regardless of the results of the A/B test, he just can't help himself and says "It was Awesome!" anyhow. If you follow his advice, you'll now win approximately 5 times for every time you lose. I'll take those odds, too.

Re: Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

#48

Post by btilly »

yummyfajitas wrote: post #41
btilly wrote: post #36

Earlier quoted context omitted.

Unfortunately most of the A/B tests that I am involved with at the moment simply do not look anything like what you'd want for a traditional bandit approach. For a start the data is fundamentally 2-dimensional. I am testing by user, and users may take days to hit a conversion metric. Furthermore a large chunk of the population has to go in the test before I get any data at all about how any of them will perform. This…

Actually you are correct that in situations with latency (i.e., you have the opportunity to play a machine at t=0, another opportunity to play at t=1, but you don't receive results of the plays until t=10), UCBx doesn't work. It's not even a question of statistical power, it's just a matter of typing. Typical bandit algorithms use the function play_machine: Machine -> Float. In the situation you describe, the type si…

The problems with UCBx in the real world are much bigger than that.

The biggest theoretical problem is how it performs when conversion rates are changing out from under it. Which can happen either because your business has natural fluctuations, or because you run overlapping tests - and adoption of one good test can mess up the analysis of unrelated tests that are running at the same time.

You can simply solve this problem by only using data collected in your exploration phase, and throwing away all data collected during exploitation for statistical purposes. However I've yet to see anyone promoting MAB approaches - including you - express any awareness of this rather significant problem.

Re: Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

#49

Post by aneth2 »

All of these solutions assume all users are the same. You could of course fragment users and test within the fragments, but how do you determine the fragments - gender? income? language? country? time of day?

Some color might work well for English speakers in China, while another might work well for Spanish speakers in the US.

Is there a way to both perform these tests, and automatically fragment results based on known facets about users?

As of now, all methods I've seen are based on the assumption that if 60% of users prefer one thing, that's the right choice. What about the 40% - how do we give them what they want?

Re: Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)

#50

Post by aneth3 »

All of these solutions assume all users are the same. You could of course fragment users and test within the fragments, but how do you determine the fragments - gender? income? language? country? time of day?

Some color might work well for English speakers in China, while another might work well for Spanish speakers in the US.

Is there a way to both perform these tests, and automatically fragment results based on known facets about users?

As of now, all methods I've seen are based on the assumption that if 60% of users prefer one thing, that's the right choice. What about the 40% - how do we give them what they want?

Post reply on HN