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

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

#51

Post by aneth3 » Mon, Jun 04, 2012, 7:08 AM UTC

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?

(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.)

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

#52

Post by aneth3 » Mon, Jun 04, 2012, 7:09 AM UTC

(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?

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

#53

Post by gcanyon » Mon, Jun 04, 2012, 8:18 AM UTC

Doesn'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?

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

#54

Post by yummyfajitas » Mon, Jun 04, 2012, 9:50 AM UTC

btilly wrote: post #48

yummyfajitas wrote: post #41

Earlier quoted context omitted.

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 p…

Could you explain the problem a little more? From what you wrote here, it sounds like the problem is that if the world changes, it can mess up your answers, and bandit will take exp(N) time to catch up.

This is a problem for A/B testing also - if the world changes after your test is finished, you just got the wrong answer. Or am I missing something?

This is why you run tests which you expect to be statistically independent of each other and why you stick to results you expect to be durable.

I'd love it if you email me about it (or post publicly on the topic). I'm thinking of writing a "real world bandit benchmarking suite" which will take into account as many such situations as possible.

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

#55

Post by polyfractal » Mon, Jun 04, 2012, 12:12 PM UTC

btilly wrote: post #45

polyfractal wrote: post #44

Earlier quoted context omitted.

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.

I don't think he was referring to the technology behind the A/B test itself, but rather the technology behind the change that was being made.

That's how I interpreted his statement. I agree with you that the actual A/B testing overhead should be minimal and fairly trivial to put into place.

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

#56

Post by btilly » Mon, Jun 04, 2012, 2:33 PM UTC

yummyfajitas wrote: post #54

btilly wrote: post #48

Earlier quoted context omitted.

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 p…

Could you explain the problem a little more? From what you wrote here, it sounds like the problem is that if the world changes, it can mess up your answers, and bandit will take exp(N) time to catch up. This is a problem for A/B testing also - if the world changes after your test is finished, you just got the wrong answer. Or am I missing something? This is why you run tests which you expect to be statistically indep…

The problem is that the world changes - constantly. What changes could mess you up? When we apply math to the real world we should assume as little as possible.

A/B testing is robust in the face of absolute changes in conversion rates so long as preferences remain consistent. Of course preferences do not always remain consistent, but that is substantially more likely to happen than that conversion rates do not budge.

Traditional MAB approaches are not robust in the face of absolute changes in conversion rates, even if preferences remain consistent. The problematic change is what happens if conversion rates improve while the worse version is ahead. Then you can come to very solidly to the conclusion that the worse version is better, and be stuck on that for a depressingly long time. The smarter the MAB algorithm, the more solidly you can make that mistake.

Is this likely? Well most businesses have regular fluctuations in conversion rates. Furthermore websites under continuous improvements are constantly introducing changes. It is therefore not uncommon to, while testing one thing, make independent changes that are likely to improve conversion rates.

But as I said, the simple change to throw away data collected during exploitation makes a MAB approach also robust in the face of absolute changes in conversion rates, as long as preferences remain consistent. Doing so increases average regret by a constant factor in the case where conversion rates never change.

(There are complications in the more than 2 arm case. In particular the fact that you're uncertain about A vs C doesn't mean that you should continue exploring version B. So some observations should count as exploration between a strict subset of the versions. But that's a technical detail.)