4 ms·
This is an interesting suggestion, but I have significant questions that I'e like to see answered. 1. Most multi-armed bandit algorithms assume that the potent
by btilly 15y ago
This is an interesting suggestion, but I have significant questions that I'e like to see answered.
1. Most multi-armed bandit algorithms assume that the potential reward for each lever is the same each time you pull it. Unfortunately web traffic does not look like this - there are daily, weekly, and monthly cycles in conversion characteristics, with large random fluctuations on top. An A/B test can ignore this - who got the better traffic is just another random factor that comes out in the statistics. How much would this impact a multi-armed bandit approach?
2. My understanding is that multi-armed bandit algorithms assume that feedback is instantaneous - pull the lever and get the answer. But this is often not true. You send a whole batch of emails before getting feedback on the first. Depending on the business, incoming users can take time to convert to paying customer. I've seen places where the average time to do so was weeks. What decision should be made in that time period of uncertainty? Worse yet, what if one version speeds up conversions relative to the other? I know how to tweak an A/B test to handle this issue (just wait then look at cohorts that should have converted under either), I don't know how to modify a multi-armed bandit algorithm to do so.
3. As a practical matter, companies don't want to keep tests going indefinitely. There is a real technical cost to maintaining a complicated mix of possible pages that can shown. You want losers to be removed from your code base. A/B testing is well-suited to doing that. A multi-armed bandit approach does not.
4. Most companies don't even do A/B testing correctly. I fear that pushing a more complex scheme makes them less likely to try it, and increases the odds of mistakes.
- noelwelsh 15y agoGood questions. I'll do my best to answer them. 1. We assume that the distribution of rewards for each lever is fixed (over the short term). This allows the reward to vary randomly so long as the average reward (over the short term -- days to weeks) is constant. There are more complex schemes, which allow for greater variation in reward, but the initial Myna offering is intended to be directly comparable to A/B testing. 2. It's not necessary to assume that feedback is instantaneous. Basically you can continue to make suggestions (pull levers) in proportion to your best estimate of their expected return and the maths holds. Very long conversion cycles will cause problems for any system, I think, as you'll spend a long time in a random walk. In these cases we recommend using a proxy measure which is correlated with conversion, if one is available. As for one option speeding up conversion, I don't think that will matter as you'll simply refine your estimate of one lever faster. I haven't thought too much about this particular issue; it would be worth doing some simulations to see. 3. Just turn off the bandit when you've satisfied with the results. That is, you can use Myna like A/B testing, and the Myna UI displays confidence bounds for this very reason, while still getting the benefits of optimising as data arrives. 4. I actually like bandit algs as there is less for the user to mess up. You don't have to worry about how much data to collect, what p value to use, and so on. Just set it running and it optimises automatically.
- storborg 15y agoRe: 3, how do you calculate confidence bounds for a bandit test? I was under the impression that traditional AB testing methodologies (e.g. z-tests, p-values, etc) broke down here, because the sample size is variable.
- noelwelsh 15y agoIt's actually simpler in the bandit case, because you're only trying to estimate the average return. You could use a Chernoff-Hoeffding bound for example, but most bandit algorithms are of the upper confidence bound variety and actually calculate a bound as part of the algorithm.
- btilly 15y agoFurther questions. 1. My experience is that this assumption can be significantly mistaken. I have seen significant daily and weekly variations in conversion rates. (They average out after a bit, but they fluctuate.) Still a small tweak could help. 2. Please do look into this one, the difference is not small. I first encountered the differential timing issue with a test of the benefits of adding a phone touch point on top of an email cycle. That extra contact moved conversions up by weeks. So after the first month it looked fantastic, but then slowly degraded over time. (There was improvement, but not enough to justify the expense.) A careful cohort analysis showed that it was not worthwhile at a point where a naive A/B test was still showing the extra touchpoint winning by a very significant margin. 3. That's reasonable. 4. In practice during A/B testing people don't worry about those things either. They just start the test, and later declare a winner. (People are much more sloppy about it than they theoretically should be...)
- noelwelsh 15y ago1. Let me be a bit more precise. The basic version of Myna assumes average reward is constant over the entire time it is active. In the language of statistics, so long as the process is stationary we're ok. We have some somewhat experimental additions that try to look for slowly changing average reward and compensate for this. I say somewhat experimental as we haven't been able to really empirically validate performance yet. In the literature there are a few different approaches to handling non-stationary systems, and I imagine this is an area we'll address further as we get Myna into more complex environments. 2. Interesting. I'll investigate when I get time. 4. Indeed. In a sense the maths is irrelevant. If you can get people actually measuring the effect of their changes the battle is mostly won. We're certainly finding that it is the ease of use that is most important to our users (echoing patio11's comment below). On the other hand, once you take the human out of the loop you open the door to much more interesting applications and this is where I think the real benefit of Myna will be.