26 ms·
20 lines of code that beat A/B testing (2012)
- zardeh 11y agoWhat I love about this example is that its the same algorithm applied in two completely different areas. This algorithm (or variants of it) can be used in place of A/B testing. The same algorithm can be applied to game playing and you get Monte Carlo Tree search, the basis of AlphaGo.
- mkj 11y agoWhy 10%? Sounds like a magic constant.
- martin_bech 11y agoI believe thats the greed factor. 90% of the time you are using the winning version of the page/button what not.
- tmaly 11y agoI remember reading this post back in 2012. I ended up getting a copy of the Bandit Algorithms book by John Myles White. Its short, but it covers all the major variations.
- PaulHoule 11y agoIt is really funny how communities don't talk. For instance, A/B testing with a 50-50 split has been baked into "business rules" framework from about as along ago as the Multi-armed bandit has been around, but nobody in that community has ever heard of the multi-armed bandit, and in the meantime, machine learning people are celebrating about the performance of NLP systems they build that are far worse than rule-based systems people were using in industry and government 15 years ago.
- wodenokoto 11y agoWhich NLP system are far worse than which rule based systems? The statement is odd for two reasons. One is that plenty of NLP is rule based, the other is that NLP isn't a form of A/B testing, which is the overall topic here..
- visarga 11y ago> in the meantime, machine learning people are celebrating about the performance of NLP systems they build that are far worse than rule-based systems people were using in industry and government 15 years ago That was not my experience. I have been researching chat bots and it would seem I can hardly find one implemented with machine learning but instead almost all are rules based. I was quite disappointed. ML for NLP is just gearing up.
- tristanj 11y agoEarlier discussion (989 points, 1407 days ago) https://news.ycombinator.com/item?id=4040022 https://news.ycombinator.com/item?id=4040022
- deleted 11y ago[deleted]
- thecatspaw 11y agoI really wish hackernews would change the date format to days, months and years, rather than just days, or the original submission date as the title attribute of "1407 days ago". Submission date is may 30, 2012
- sideproject 11y agoI digress, but this site has an interesting comments layout..
- aub3bhat 11y ago"Like many techniques in machine learning, the simplest strategy is hard to beat." is a thoroughly ridiculous statement. It should instead say "Like many techniques in machine learning, the simplest strategy is easiest to implement" as the title of the post (20 lines) makes it clear.
- argonaut 11y agoThat's not thoroughly ridiculous. For many problems in machine learning, k-nearest-neighbors and a large dataset is very hard to beat in terms of error rate. Of course, the time to run a query is beyond atrocious, so other models are favored even if kNN has a lower error rate.
- deleted 11y ago[deleted]
- mortehu 11y agoAccording to [1], k-NN is pretty far from being the top general classifier. Admittedly, all the data sets are small, with no more than 130,000 instances. When does it start becoming "very hard to beat", and what are you basing that on? 1. http://jmlr.org/papers/volume15/delgado14a/delgado14a.pdf http://jmlr.org/papers/volume15/delgado14a/delgado14a.pdf
- argonaut 11y agoThe vast majority of the data sets are very small (on the order of 100 to 1000 examples!). In fact, in the paper they discarded some of the larger UCI datasets. It's not surprising that they found random forests perform better, even though the conventional wisdom is boosting outperforms (it's much harder to overfit with forests).
- coldtea 11y agoNot just easiest to implement -- literally "hard to beat". Not "impossible to beat" mind you -- merely hard. Because the simplest strategies work so well in so many cases, that you need to go quite subtle and implement harder algorithms (doesn't matter if you just take them ready off of a lib for the argument) to see an improvement. 80-20, et al.
- thecopy 11y agoOfftopic, but why do i have to enable Javascript to even see anything?
- kqr 11y agoThat is really weird. Technically the content is there all along (so it's not loaded in by JavaScript) but you still have to have JavaScript enabled for it to render. Who designed that!? Edit: hahaha what. It appears the content is laid out with JavaScript. So basically they're using JavaScript as a more dynamic CSS. Let that sink in. They're using JavaScript as CSS. It sorta-kinda makes sense for the fancy stream of comments but still... why is it a requirement!?
- pdkl95 11y agoApparently some sort of useless fade-in effect is more important than the page content. This is the fix: #main { visibility: visible !important; }
- coldtea 11y agoTheir trick also keeps noscript weirdos out though, which is a plus.
- pdkl95 11y agoNo, it didn't. I'm not about to run random Javascript, and the page was visible within ~3 clicks. Page that are actually broken without Javascript only indicate that the author was lazy and unprofessional. Progressive enhancement is not hard.
- coldtea 11y ago>Page that are actually broken without Javascript only indicate that the author was lazy and unprofessional. Or that they have kept with the times and understand the notion of opportunity cost. >Progressive enhancement is not hard. No, just redundant and for marginal benefit. The train has long left that station. Search Engines (well, those that matter) and screen readers for a11y both work with JS.
- ReadingInBed 11y agoI thought this was a pretty good follow up to show the strengths and weaknesses of this approach: https://vwo.com/blog/multi-armed-bandit-algorithm/ https://vwo.com/blog/multi-armed-bandit-algorithm/. Personally I think this approach makes a lot more sense than a/b testing especially when often people hand off the methodology to a 3rd party without knowing exactly how they work.
- aidanf 11y agoHere are 2 good articles that follow up on the arguments presented by VWO in that article. From the first link below: "They do make a compelling case that A/B testing is superior to one particular not very good bandit algorithm, because that particular algorithm does not take into account statistical significance. However, there are bandit algorithms that account for statistical significance." * https://www.chrisstucchio.com/blog/2012/bandit_algorithms_vs_ab.html https://www.chrisstucchio.com/blog/2012/bandit_algorithms_vs... * https://www.chrisstucchio.com/blog/2015/dont_use_bandits.html https://www.chrisstucchio.com/blog/2015/dont_use_bandits.htm...
- paraschopra 11y agoChris is now VWO's director of data science. We recently overhauled our stats. Here's a quick summary for that: https://vwo.com/blog/smartstats-testing-for-truth/ https://vwo.com/blog/smartstats-testing-for-truth/
- raverbashing 11y ago
- saturdayplace 11y agoSo I googled A/B testing vs Multi-Armed Bandit, and ran into an article that's a useful and informative response to the OP: https://vwo.com/blog/multi-armed-bandit-algorithm/ https://vwo.com/blog/multi-armed-bandit-algorithm/ edit: Ah, 'ReadingInBed beat me to it. tl;dr: Bandit approaches might not _always_ be the best, and they tend to take longer to reach a statistically significant result.
- 3dfan 11y ago10% of the time, we choose a lever at random. The other 90% of the time, we choose the lever that has the highest expectation of rewards. There is a problem with strategies that change the distribution over time: Other factors change over time too. For example let's say over time the percentage of your traffic that comes from search engines increases. And this traffic converts better then your other traffic. And let's say at the same time, your yellow button gets picked more often then your green button. This will make it look like the yellow button performs better then it actually does. Because it got more views during a time where the traffic was better. This can drive your website in the wrong direction. If the yellow button performs better at first just by chance then it will be displayed more and more. If at the same time the quality of your traffic improves, that makes it look like the yellow button is better. While in reality it might be worse. In the end, the results of these kinds of adaptive strategies are almost impossible to interpret.
- zeckalpha 11y agoIt's possible to weight conversions by frecency to account for this, rather than using frequency alone.
- kevin_nisbet 11y agoI don't know if this is the case if I understand this algorithm correctly. Say Yellow is 50%, and Green is a 65% success rate after the behavior change, but green is 30% before the behavior change. By sending 90% of traffic towards yellow, it's ratio will normalize towards the 50% once it has enough traffic. By sending 10% of traffic randomly, eventually the green option will reach 51%, and start taking a majority of traffic, which then will cause it to normalize at it's 65%, and be shown to a majority of users. I think the problem might be, if you run this with a sufficiently high volume or for a long period of time, that if a behaviour change takes place it will take a long time to learn the new behaviour. Or if two options aren't actually different, it may continually flip back and fourth between two options. Also, to me, the concept of A/B testing certain things may also have an undesired consequence. For example, I order from amazon every day, but today the but button is blue, what does that actually mean? And I go back to the site later and it's yellow again. There are still many people who get confused by seemingly innocuous changes with the way their computer interacts with them.
- spiderfarmer 11y agoI did a lot of A/B testing, but I think the examples that are used in a lot of articles about A/B testing are weird. For small changes like change the color / appearance of a button, the difference in conversion rate is not measurable. Maybe if you can test with traffic in the range of >100K unique visitors (from the same sources), you can say with confidence which button performed better. But how many websites / apps really have >100K uniques? If you have a long running test, just to gather enough traffic, changes are some other factors have changed as well, like the weather, weekdays / weekends, time of month, etc. And if you have <100K uniques, does the increase in conversion pay for the amount of time you have invested in setting up the test? In my experience, only when you test some completely different pages you'll see some significant differences.
- mangeletti 11y ago> the difference in conversion rate is not measurable Wut? Here's the results of me changing an "add to cart" button from a branded looking maroon button to a simple yellow (Amazon style) button: http://cl.ly/0d440I3T333m http://cl.ly/0d440I3T333m That's 26% sales increase from changing a button's color. If you've got a good eye for usability, your intuition is going to lead to a lot of fun and great results with A/B testing. If not, you'll futz with things that make no difference most of the time and eventually give up. Experimentation is not about testing random permutations (unless you've got an infinite amount of time). It's about coming up with a reasonable hypothesis and then testing it. I study a web page until I come to a conclusion in my mind that something could really use some improvement. Then, even though I'm sure of it in my mind, I test it, because "sure of it in my mind" is wrong about half the time. One note to those who use Optimizely: you do need to wait at least twice as long as Optimizely thinks, because statistical significance can bounce around with too little traffic. Optimizely thought the above test was done at about 2000 views, which was far too little results to be conclusive, with only ~20 sales.
- rco8786 11y agoYou really should question the statistical significance of those numbers.
- gaz 11y agothere is a startup (unlaunched) built around this approach http://www.growthgiant.com http://www.growthgiant.com
- tarsinge 11y agoA/B Tasty (most used platform in France I think, not affiliated) uses this approach : http://blog.abtasty.com/en/clever-stats-finally-statistics-suited-to-your-needs/ http://blog.abtasty.com/en/clever-stats-finally-statistics-s...
- davkap92 11y agoInteresting but since the writing of this article (2012) Google do offer Multi Armed Banned Content Experiments... https://support.google.com/analytics/answer/2844870?hl=en https://support.google.com/analytics/answer/2844870?hl=en
- adurgavich 11y agoThis is exactly what Adobe is already doing with its 1:1 product. But the fact is a 10% of traffic for a medium-size website won't get you the results you want quickly. 10% of traffic only works on enterprise-level websites.
- pitchka 11y agoJohn Langford and the team (Microsoft Research) have built a contextual bandit library in Vowpal Wabbit. It can be used from active learning to changing webpage layouts to increase ad clicks. It has the best bounds out of all exploratory algorithms. Structured contextual bandits that come with LOLS (another algorithm present in vowpal wabbit) is extremely powerful. All for free under BSD3.
- ryporter 11y agoThis is a good overview of the multi-arm bandit problem [1], but the author is far too dismissive of A/B Testing. First of all, the suggested approach isn't always practical. Imagine that you are testing an overhaul of your website. Do you want daily individual visitors to keep flipping back and forth as the probabilities change? I'm not sure if the author is really suggesting his approach would be a better way to run drug trials, but that's clearly ridiculous. You have to recruit a set of people to participate in the study, and then you obviously can't change what drug you're giving them during the course of experiment! Second, it ignores the time value of completing an experiment earlier. In the exploration/exploitation tradeoff, sometimes short-term exploitation isn't nearly as valuable as wrapping up an experiment so that your team can move to new experiments (e.g., shuting down the old website in the previous example). If a company expects to have a long lifetime, then, over the a time frame measured in weeks, exploration will likely be relatively far more valuable. [1] https://en.wikipedia.org/wiki/Multi-armed_bandit https://en.wikipedia.org/wiki/Multi-armed_bandit
- davkap92 11y agoRegarding your first point, not sure if author covered it, but in Google Content Experiments with multi bandit approach cookies are stored, so user who sees variation b will keep seeing b while the experiment is running
- mplewis 11y agoThis is the approach every good AB testing service/framework uses.
- shade23 11y agoA side note: I love the website UX/Design. Especially the flowing comments layout.
- imaginenore 11y agoMultivariate A/B testing lets you test combinations of multiple changes simultaneously.
- mabbo 11y agoThis presumes a few of things about the decision being tested, many of which aren't always true. I ran a few basic A/B tests on some handscanner software used in large warehouses. The basic premise is that the user is being directed where to go and what items to collect. The customer wanted to know how changes to font size and colour of certain text would improve overall user efficiency. But the caveat was that we had to present a consistent experience to the user- you can't change the font size every 10 seconds or it will definitely degrade user experience! My point is that it sounds as though the 1-armed bandit will probably work great provided the test is short, simple, and the choice can be re-made often without impacting users.
- zeckalpha 11y agoIt's possible to assign a user to a category once a week, and use the same algorithm, rebalancing users between the categories as needed once a week.
- orasis 11y agoI've been using bandits in my mobile apps for the last 3 years and am now packaging them as a saas REST API. Message me if you want an early look.
- katafalkas 11y agoHey, I was working on the same thing. Wanna talk about it ?
- orasis 11y agoHere's what everyone is missing. Don't use bandits to A/B test UI elements, use them to optimize your content / mobile game levels. My app, 7 Second Meditation, is solid 5 stars, 100+ reviews because I use bandits to optimize my content. By having the system automatically separate the wheat from the chaff, I am free to just spew out content regardless of its quality. This allows me to let go of perfectionism and just create. There is an interesting study featured in "Thinking Fast and Slow" where they had two groups in a pottery class. The first group would have the entirety of their grade based on the creativity of a single piece they submit. The second group was graded on only the total number of pounds of clay they threw. The second group crushed the first group in terms of creativity.
- whatever_dude 11y agoLove that example, even if frequently retold. http://blog.codinghorror.com/quantity-always-trumps-quality/ http://blog.codinghorror.com/quantity-always-trumps-quality/
- deleted 11y ago[deleted]
- mrspeaker 11y agoI don't understand what you mean by "use them to optimize your content" - how are you doing that with your app? Are you serving different messages to different groups of people? How are you grouping/testing/rating them?
- andreasklinger 11y agoi dont know the app but i assume he has a core action (-> which he iterates/churns out) and evaluates if people act (-> used as rating) eg (guesses here) new notification types "think for 9 seconds about a loved one" "what was your favorite vacation, go there" if people act -> reward and reuse if not -> reuse less (only by random chance) alternative to notification could be "completed medidation screen"
- orasis 11y ago
- paulsutter 11y agoAuthor is confusing the map and the territory. A/B testing is comparing the performance of alternatives. Epsilon-greedy is a (good) way to do that. it's better than the most common approach, but you're still testing A against B.
- conductrics 11y agoWhen thinking about what type of approach is best, first think about the nature of the problem. First is it a real optimization problem, IOW are you more concerned with learning an optimal controller for your marketing application? If so then ask: 1) Is the problem/information perishable - for example Perishable: picking headlines for News articles; Not Perishable: Site redesign. If Perishable then Bandit might give you real returns. 2) Complexity: Are you using covariates (contextual bandits, Reinforcement learning with function approximation) or not. If you are, then you might want your targeting model to serve up best the predicted options in subspaces (frequent user types) that it has more experiences in and for it to explore more in less frequently visited areas (less common user types). 3) Scale/Automation: You have tons of transactional decision problems, and it just doesn't scale to have people running many AB Tests. Often it is a mix - you might use a bandit approach with your predictive targeting, but you also should A/B tests the impact of your targeting model approach vs a current default and/or a random draw. see slides 59-65: http://www.slideshare.net/mgershoff/predictive-analytics-broken-down http://www.slideshare.net/mgershoff/predictive-analytics-bro... For a quick bandit overview check out: http://www.slideshare.net/mgershoff/conductrics-bandit-basicsemetrics1016 http://www.slideshare.net/mgershoff/conductrics-bandit-basic...
- hoddez 11y agoThere is at least one caveat with multi-armed bandit testing. It assumes that the site/app remains constant over the entire experiment. This is often not the case or feasible, especially for websites with large teams deploying constantly. When your site is constantly changing in other ways, dynamically changing odds can cause a skew because you could give more of A than B during a dependent change, so you have to normalize for that somehow. A/B testing doesn't have this issue because the odds are constant over time.
- dalacv 11y agoA post on why the bandit is not better: https://vwo.com/blog/multi-armed-bandit-algorithm/ https://vwo.com/blog/multi-armed-bandit-algorithm/
- llull 11y agoBandits are great, but using the theory correctly can be difficult (and if accidentally incorrectly applied then ones results can easily become pathologically bad). For instance, the standard stochastic setup requires that learning instances are presented in an iid manner. This may not be true for website visitors, for example different behaviour at different times of day (browsing or executing) or timezone driven differing cultural responses. There is never a simple, magic solution for these things.
- sixtypoundhound 11y agoNovices also tend to gravitate towards "end-game" business metrics which have a lot more inherent variation than simple operational indicators. For example - optimizing a content site for AdSense; many folks would gravitate to AdSense $$ as the target metric, which is admittedly an intuitive solution (since that's how you're ultimately getting paid). But if you think about it.... AdSense Revenue => (1 - Bounce Rate) x Pages / Visit x % ads clicked x CPC Bounce rate is binomial probability with a relatively high p-value (15%+), thus you can get statistically solid reads on results with a relatively small sample. Pages / Visit is basically the aggregate of a Markov chain (1 - exit probability); also relatively stable. % ads clicked - binomial probability with low p-value; large samples becomes important $ CPC - so the ugly thing here is there's a huge range in the value of a click... often as low as $.05 for a casual mobile phone click or $30 for a well qualified financial or legal click (think retargeting, with multiple bidders). And you're usually dealing with a small sample of clicks (since the average % CTR is very low). So HUGE natural variation in results. Oh, and Google likes to penalty price sites with a large rapid increase in click-through-rate (for a few days), so your short term CPC may not resemble what you would earn in steady-state. So while it may make ECONOMIC sense to use test $ RPM as a metric, you've injected tremendous variation into the test. You can accurately read bounce rate, page activity, and % click-through on a much smaller sample and feel comfortable making a move if you're confident nothing major has changed in terms of the ad quality (and CPC value) you will get.
- trjordan 11y agoIsn't that a good argument for using $$ as the metric to optimize for? If you're going to get wiped out by variations in behavior because highly-retargeted legal clicks are worth 500x more than mobile clicks, isn't that an important variable? The problem I frequently wonder about is that you have to assume independence about the stable variables to be comfortable testing them. In reality, the bounce rate of a people who make you lots of money is probably driven by different factors than the bounce rate of the overall population. I guess what you should really do is optimize the bounce rate / pages per visit / etc. for just the population of people that could make you money, but you don't typically have access to that information.
- chias 11y agoI like the premise of this a lot, but it seems to me that the setting that the author chose (some UI element of a website) is one of the worst possible settings for this: what matters a whole lot more than if your button is red or green or blue is some modicum of consistency. If you're constantly changing the button color, size, location, whatever... that is an awful experience in and of itself, is it not? If the Amazon "buy now" button changed size / shape / position / color every time I went to buy something, I would get frustrated with it pretty quickly.
- tswartz 11y agoIf you cookie the users and make sure the experience they saw is persistent that solves most of this problem. But if you run a lot of separate tests than it's hard to avoid this.
- blakeyrat 11y agoOne aspect of testing they leave unsaid is you identify your users (cookie, most commonly) to make sure each user always gets the same experience. That's why your numbers are all based on unique users, not merely users. Their experience will still change once their cookie expires, but that amount of time is completely under your control.
- cle 11y agoThis is only appropriate in certain situations. There are many business situations in which it's more appropriate to run a traditional A/B test and carefully examine and understand the results before making a business decision. Always blindly accepting the results of a bandit is going to explode in your face at some point. There is no silver bullet, no free lunch. There is no algorithm that will beat understanding your domain and carefully analyzing your data.
- jedberg 11y agoJust a warning, this isn't a magic bullet to replace all A/B testing. This is great for code that has instant feedback and/or the user will only see once, but for things where the feedback loop is longer or the change is more obvious or longer lasting (like a totally different UI experience), it doesn't work so well. For example, if your metric of success is that someone retains their monthly membership to your site, it will take a month before you start getting any data at all. At that point, in theory almost all of your users should already be allocated to a test because hopefully they visited (and used) their monthly subscription at least once. So it would be a really bad experience to suddenly reallocate them to another test each month.
- scottlocklin 11y agoReinforcement approaches are certainly interesting, but one of the things missing here (and in most A/B stuff) is statistical significance and experimental power. If you have enough data, there are hand wavey arguments that this will eventually be right, but in the meanwhile, if there is some opportunity cost (say, imagine this is a trading algo trying to profit from bid/ask), you screwed yourself out of some unknown amount of profits. There actually ways of hanging a confidence interval on this approach which virtually nobody outside the signal processing and information theory communities know about. Kind of a shame.
- gburt 11y agoAny chance you could point me to a reference? I'm doing research in this space and currently working on a paper which does exactly this for diagnostics of testing processes.
- scottlocklin 11y agoI'm not sure which thing I mentioned you need a reference on. For p-values on machine learning techniques, http://vovk.net/cp/index.html http://vovk.net/cp/index.html I'll eventually do a blog post on this subject; it's very good math that all ML people should know about, though Vovk, Schaefer and Gammerman write pretty dense articles. For statistical power... "Statistical Power Analysis for the Behavioral Sciences" by Jacob Cohen.
- gburt 11y agoSorry, I intended to quote your last sentence, applying a confidence interval to a reinforcement learning system, especially with respect to multi-armed bandits / adaptive experiments, but if I have to dig in to some signal processing stuff I am happy to do that. It seems the conformal prediction link has some relation. I will dig, thanks.
- scottlocklin 11y agoYes, conformal prediction does exactly this.
- Zyst 11y agoThought this was interesting, so I made it in C#. I could've optimised a bit more in the Choose function but regardless, this is super cool! https://gist.github.com/Zyst/0da505007b0e8c21418247000f3e7d40 https://gist.github.com/Zyst/0da505007b0e8c21418247000f3e7d4...
- creade 11y agoOne of the best talks I've ever seen was Aaron Swartz talking about how Victory Kit used multi-armed bandits to optimize political action: https://github.com/victorykit/whiplash https://github.com/victorykit/whiplash
- wnevets 11y agoisn't this how a/b testing works with google analyitcs?