8 ms·
Why Multi-armed Bandit algorithms are superior to A/B testing (with Math)
- raverbashing 14y agoWhat, now it's indirect argument over HN? Dear UX specialists with no knowledge of statistics: you can use the MAB algo with 2 choices, no problem. And it is a better way of getting 'the right choice'. Dear statisticians: there's more to life (and to UX) than A/Bing (or MABing) everything
- _delirium 14y agoI don't think most statisticians need to be taught the latter. This particular narrow slice of statistical methodology is dominant in certain areas of advertising, web design, and UX, but it's not as if it completely dominates the field of statistics, or the toolbox of most statisticians.
- dwc 14y ago> What, now it's indirect argument over HN? This has obviously been standard procedure for a while now. I see this on almost a daily basis. Afraid your comment on a HN thread won't get enough traction? Make a blog post instead, meant expressly for submission to HN (or reddit, or ...)
- btilly 14y agoDear random internet poster. This argument has happened several times already on this site. I recommend reading previous discussion at http://news.ycombinator.com/item?id=4052997 http://news.ycombinator.com/item?id=4052997 and http://news.ycombinator.com/item?id=4040022 http://news.ycombinator.com/item?id=4040022 before being sure that this blog is obviously the final say.
- Anirak 14y agoNext: "why we're leaving bandit and A/B testing"
- noelwelsh 14y agoLet'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.
- dwc 14y agoFirst off, I'm all for settling this with data and math. However, I'm afraid that some practical matters were lost in the previous discussions. As I see it, things happened somewhat like this: 1) A/B testing starts to become a Big Deal; 2) There's a flurry of articles about A/B testing of various quality; 3) Lots of people implement A/B testing, mostly in a poor way; 4) The 20 lines of code article, which would probably really help most people who haven't done A/B testing correctly; 5) Intense discussion about correctness and efficacy that won't impact those people. I think getting to the bottom of this is important, but I think the multi-armed bandit article that started this would do far more good than harm for the droves of people trying and largely failing to get good data from their poorly done A/B testing.
- noelwelsh 14y agoI'm all for multi-armed bandits. So much so that I've founded a startup to bring them to the masses (http://mynaweb.com/ http://mynaweb.com/ Sign up now!) I'm absolutely certain that an appropriate MAB algorithm will outperform A/B in the overwhelming majority of cases and be simpler and flexible to use in practice. However some reasonable objections have been raised in the previous discussions. (In case anyone is keeping record, here are the ones I have been involved in: - http://news.ycombinator.com/item?id=4052997 http://news.ycombinator.com/item?id=4052997 - http://news.ycombinator.com/item?id=4040022 http://news.ycombinator.com/item?id=4040022 - http://news.ycombinator.com/item?id=3928929 http://news.ycombinator.com/item?id=3928929 - http://news.ycombinator.com/item?id=3867380 http://news.ycombinator.com/item?id=3867380 - http://news.ycombinator.com/item?id=2831455 http://news.ycombinator.com/item?id=2831455 ) The typical way for a company to handle these objections would be to ignore them or publish a few pretty graphs and drown the objections in FUD. I think the community deserves better, and would like to do a proper comparison. It will not only be informative but also help us design a better algorithm. Everyone wins.
- luigi 14y agoSo am I getting this right? (Edit) So the two steps to run are: 1. Run a traditional A/B test until 95% confidence is reached. This is full exploration. 2. Then, switch to the MAB after that, showing the better performing variant most of the time. As time increases, the display of the worse performing variants decreases.
- kevinconroy 14y agoThis article suggests another option: Run UCB1 (a specific MAB variation) from day one and you'll get benefits of MAB without limitations of A/B testing or mathematical fallacies of the prior 20 lines of code MAB for n-cell tests.
- luigi 14y agoI thought the article was suggesting that step #1 is part of UCB1?
- aaronjg 14y agoOption 1 will NOT give you the correct answer. You CANNOT use confidence intervals as a stopping criteria. If you do this, you end up running many tests, and then you need to apply a multiple test correction to account for this. Otherwise you run a VERY HIGH risk of picking the wrong result. I emphasize, because this is a common problem made by A/B test practitioners. For a fuller discussion of the problems, check out the papers by Armitage (frequentist) and Anscombe (Bayesian) on the topic. Or see my summary of the issue here: http://blog.custora.com/2012/05/a-bayesian-approach-to-ab-testing/ http://blog.custora.com/2012/05/a-bayesian-approach-to-ab-te...
- luigi 14y agoSorry I wasn't clear. I meant run #1 first, then run #2. I didn't mean them as different options.
- mxfh 14y agoWhat is is the half-time rate of this debate? 300 days or less? http://news.ycombinator.com/item?id=2831455 http://news.ycombinator.com/item?id=2831455 Sadly, the option to drop this problem over Germany doesn't exist any more.[1] [1] http://en.wikipedia.org/wiki/Multi-armed_bandit#Empirical_motivation http://en.wikipedia.org/wiki/Multi-armed_bandit#Empirical_mo...
- ygmelnikova 14y agoMy guess is 98% of developers use neither.
- patio11 14y agoYou are, sadly, overshooting the worldwide population of A/B testing developers by at least an order of magnitude. Great news for my consulting business, bad news for everyone else.
- patio11 14y agoFor what it's worth, I've been following this cross-Internet debate with more than a little professional interest. Cards on the table: I have coded A/B testing software, I frequently code and/or administer it for clients (often in ways which are provably suboptimal), and I am a dirty loyalty-free scientist-cum-capitalist-pig who would stab A/B testing in the back in a second if I thought there were an easier way to extract more money for the same amount of work. I strongly, strongly suggest that anyone attempting to look at this problem from the perspective of a site owner rather than a mathematical abstraction read and digest btilly's comment from earlier this week: http://news.ycombinator.com/item?id=4040616 http://news.ycombinator.com/item?id=4040616 The issues he lays out are very real in the course practical use of site testing to actually make money. In particular, his #2 would scare the heck out of me, in a much deeper way than "A/B testing provably doesn't minimize regret" worries me in the other direction. (Or e.g. other flaws with particular A/B testing implementations. For example, repeatedly checking the results of your A/B test and deciding to end it when you see significance has been explained quite a few times as a bad idea with stats to match. However, even if you check like a hyperactive squirrel, you're still winning, you're just winning less often than you think you are. Take your B- in stats class but proceed to make motivational amounts of money for the business.) The worst possible takeaway you, personally, the typical HN reader, could possibly have from this debate is "Oh, I guess I shouldn't A/B test then." 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. (Actually testing today also is better than "testing... someday", which from my own experience and that of clients I know is something which is very easy to slip into even if you theoretically know you should be doing it.)
- yummyfajitas 14y agoPick 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 thing. Bad A/B testing is an 80% solution. Good A/B testing is a 90% solution. Good bandit is a 95% solution. 80% >> 0. A/B testing has another benefit to software engineers that bandit doesn't - it lets you delete code.
- blueskittle 14y agoAs 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 these testing methods: 1. Implementation Costs - How much time will it take to implement the testing code? Some tests are easier to implement than others. 2. Maintenance Costs - How much time will it cost to maintain the test for the duration of the testing period? We've ignored this in the past only to realize on occasion that implementation introduces bugs which incur cost and can be disruptive. 3. Opportunity Costs - What is the cost of doing the test versus not doing the test? Consider setup time, analysis, and final implementation. After going through a few tests now, we have a pretty good sense for what the total cost to the business is. We don't really look at it as adopting one test method over the other, but instead rely upon the projected ROI to test this versus that, versus doing nothing.
- btilly 14y agoIf 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, B => 1}); where test is the name of a test, and 1234 is a ticket number to avoid accidental conflicts of test names. The other appears in a template and looks something like this: .../[% ab_test.test_12345 == 'A' ? 'button1' : 'button2' %].png... That's it. The test automatically shows up in a daily reports. When it wins, you get rid of that code and put the right thing in the template. Done.
- polyfractal 14y agoI 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.
- tmoertel 14y agoWhat’s being glossed over here, and explains a lot of the confusion around which is the best method of “solving” the multi-arm-bandit problem, is the classical bias-variance tradeoff. All of the methods presume some model of the problem, and some of those models are more flexible than others. When a model is more flexible, it allows solutions to take on more shapes and must burn more of its training data choosing among those shapes. Models that are more biased toward a particular shape, on the other hand, can use more of their data for convergence and so converge more rapidly. Which method is “best” depends on what you know about the problem. Does its optimal solution look a certain way? change over time? and so on. If you’re willing to bet on your answers to those questions, you can choose a method that’s biased toward your answers, and you’ll converge more rapidly on a solution. The risk, however, is that you’ll bet wrong and converge on a poor solution (because your biases rule out better solutions). If you’re not willing to bet on your answers, you can choose a method that will place bets for you based on what it sees in the data. But now you’re burning some of your data on betting. So that’s the tradeoff: you can use more of your knowledge to place bets (and risk placing the wrong bets), or more of the data’s knowledge to place bets (and burn some of your data on betting). Where you adjust the slider between those two is up to you. Which brings us back to our original question. Which method of solving the multi-arm-bandit problem is best? It depends a lot on where you want to adjust the slider. Which depends on your knowledge, aversion to risk, and expected payoffs. In life, sometimes one size does not fit all. If you’re going to test one shoe size against another, make sure you know which foot will end up wearing the winner. Likewise, if you’re going to compare algorithms for solving the multi-arm-bandit problem, make sure know the particulars of the problem you need to solve.
- conductrics 14y agoDisclaimer: 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 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 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.
- aneth2 14y agoAll 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?
- aneth3 14y agoAll 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?
- aneth3 14y agoAll 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? (I'm trying to ask a legitimate question here but seem to be filtered by HN's impossibly bad spam/hellbanning system. Perhaps this text will make this post different enough or provoke a hellban.)
- aneth3 14y ago(I'm trying to ask a legitimate question here but seem to be filtered by HN's impossibly bad spam/hellbanning system. Perhaps this text will make this post different enough or provoke a hellban.) 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?
- gcanyon 14y agoDoesn't this method also (over) simplify? It goes into pseudo explorer mode anytime there is a >0 probability that the presumed worst cast is actually better than the presumed best/better case. Shouldn't there be a threshold to that process, so that the presumed worst case must have at least a (for example) .05 probability of being better before the algorithm gives it a shot?