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

Why multi-armed bandit algorithm is not "better" than A/B testing

visualwebsiteoptimizer.com

Post reply on HN
Print view View original

61–70 of 80 posts

Re: Why multi-armed bandit algorithm is not "better" than A/B testing

#61

Post by btilly »

sparsevector wrote: post #57
btilly wrote: post #50

(For previous discussion on this topic, see http://news.ycombinator.com/item?id=4040022. ) Let's stop a bad meme before it gets going. Multi-armed bandit is a general problem. There are many strategies for tackling it. An epsilon-greedy strategy is one strategy. It is not the only strategy, and it is not even a particularly good one. There are many others. In fact A/B testing is itself a solution to the multi-armed b…

> I believe that I can produce a multi-armed bandit algorithm that has logarithmic regret and will work in the face of ever varying conversion rates, as long as there is a consistent relative difference between the versions. That sounds interesting. As you undoubtedly know, there is a lot of literature on multi armed bandit problems and also on the non-stochastic multi armed bandit problem. The latter has the advanta…

I know there is a lot of literature, which I'm unfortunately less familiar with than I'd like to be.

Here is the specific problem that I am interested in.

Suppose we have a multi-armed bandit where the probability of reward are different on every pull. The distribution of rewards are not known. It is known that there is one arm which, on every pull, has a minimum percentage chance by which it is more likely to produce a reward if pulled than any other arm. Which arm this is is unknown, as is the minimum percentage.

In other words payoff percentages change quickly, but the winner is always a winner, and your job is to find it. I have an algorithm that succeeds with only logarithmic regret. I have no idea whether anyone else has come up with the same idea, and there is so much literature (much of which I presume is locked up behind paywalls) that I cannot easily verify whether anyone else has looked at this variant.

Re: Why multi-armed bandit algorithm is not "better" than A/B testing

#62

Post by timr »

brockf wrote: post #48
jerf wrote: post #37

Earlier quoted context omitted.

"People are still randomly assigned to one of the conditions in the MAB scheme" No, they're only partially randomly assigned to one of the conditions. MAB has a memory based on what the results of the previous runs are, which is basically another way of phrasing that there's a dependence.

I'm not so sure. By that logic, no experiment has random assignment. I know when I place subject X in condition Y that I do so because I need Z people in condition Y. Thus, I have some information about where I've placed other people. This is no different?

The point is that with bandit models, you're placing people in a cohort as a function of the previous conversion rate of your cohorts. That's the dependence.

By contrast, randomly allocating X% of your population to cohort C_i is not a dependence on anything but the free parameter (X).

Re: Why multi-armed bandit algorithm is not "better" than A/B testing

#63

Post by sparsevector »

btilly wrote: post #61
sparsevector wrote: post #57

Earlier quoted context omitted.

> I believe that I can produce a multi-armed bandit algorithm that has logarithmic regret and will work in the face of ever varying conversion rates, as long as there is a consistent relative difference between the versions. That sounds interesting. As you undoubtedly know, there is a lot of literature on multi armed bandit problems and also on the non-stochastic multi armed bandit problem. The latter has the advanta…

I know there is a lot of literature, which I'm unfortunately less familiar with than I'd like to be. Here is the specific problem that I am interested in. Suppose we have a multi-armed bandit where the probability of reward are different on every pull. The distribution of rewards are not known. It is known that there is one arm which, on every pull, has a minimum percentage chance by which it is more likely to produc…

I think what you're describing is basically the non-stochastic setting. The idea there is to assume absolutely nothing about the rewards (they can be generated by quickly changing distributions or even an adversary) but still try to do as well as the best single arm. The standard algorithm for this problem is the multiplicative weights update method, also called the exponentially weighted average method or the hedge algorithm. It's a really simple method where you keep a probability distribution over the arms and then reweight the probabilities at each time step using something proportional to the exponential of the rewards of the arms. If you run it for T time steps on a problem involving N arms, it gives you regret O(sqrt(T log N)). This is actually the best possible bound without additional assumptions. This is a good paper on it: http://cns.bu.edu/~gsc/CN710/FreundSc95.pdf

There are many, many different variations of the method and result. For example, you can show improved results assuming different things about the rewards. For exapmle, you can show O(log(T)) regret with certain additional assumptions. This is a really good book on different non-stochastic online learning problems: http://www.ii.uni.wroc.pl/~lukstafi/pmwiki/uploads/AGT/Predi...

Re: Why multi-armed bandit algorithm is not "better" than A/B testing

#64

Post by guelo »

My imaginary ideal would be a genetic algorithm that mutates the HTML and CSS in random ways. You'll probably have users with completely unusable pages but that's the price you pay for finding the optimal solution as it converges over time, probably a really, really long time.

Re: Why multi-armed bandit algorithm is not "better" than A/B testing

#65

Post by btilly »

sparsevector wrote: post #63
btilly wrote: post #61

Earlier quoted context omitted.

I know there is a lot of literature, which I'm unfortunately less familiar with than I'd like to be. Here is the specific problem that I am interested in. Suppose we have a multi-armed bandit where the probability of reward are different on every pull. The distribution of rewards are not known. It is known that there is one arm which, on every pull, has a minimum percentage chance by which it is more likely to produc…

I think what you're describing is basically the non-stochastic setting. The idea there is to assume absolutely nothing about the rewards (they can be generated by quickly changing distributions or even an adversary) but still try to do as well as the best single arm. The standard algorithm for this problem is the multiplicative weights update method, also called the exponentially weighted average method or the hedge…

The article is interesting, but assumed you get to pull all of the arms at once, and see all of the results. That's different from the website optimization problem.

The book looks like it would take a long time to work through, and they don't get to the multi-armed bandit problem until chapter 6. It goes into my todo list, but is likely to take a while to get off of it...

Re: Why multi-armed bandit algorithm is not "better" than A/B testing

#66

Post by Estragon »

timr wrote: post #62
brockf wrote: post #48

Earlier quoted context omitted.

I'm not so sure. By that logic, no experiment has random assignment. I know when I place subject X in condition Y that I do so because I need Z people in condition Y. Thus, I have some information about where I've placed other people. This is no different?

The point is that with bandit models, you're placing people in a cohort as a function of the previous conversion rate of your cohorts. That's the dependence. By contrast, randomly allocating X% of your population to cohort C_i is not a dependence on anything but the free parameter (X).

The results will still be conditionally independent given the assignments, which is all you need to use the counts for estimation of a binomial .

Re: Why multi-armed bandit algorithm is not "better" than A/B testing

#67

Post by noelwelsh »

sparsevector wrote: post #63
btilly wrote: post #61

Earlier quoted context omitted.

I know there is a lot of literature, which I'm unfortunately less familiar with than I'd like to be. Here is the specific problem that I am interested in. Suppose we have a multi-armed bandit where the probability of reward are different on every pull. The distribution of rewards are not known. It is known that there is one arm which, on every pull, has a minimum percentage chance by which it is more likely to produc…

I think what you're describing is basically the non-stochastic setting. The idea there is to assume absolutely nothing about the rewards (they can be generated by quickly changing distributions or even an adversary) but still try to do as well as the best single arm. The standard algorithm for this problem is the multiplicative weights update method, also called the exponentially weighted average method or the hedge…

I don't think the non-stochastic setting is entirely appropriate. What we've been discussing is a situation where the differences in conversion rates are constant in expectation, though absolute conversion rates vary. So it's basically a stochastic setting, which should allow more leverage. Also, as I recall for the non-stochastic setting the definition of regret changes so the regret bounds are not directly comparable.

Re: Why multi-armed bandit algorithm is not "better" than A/B testing

#68

Post by sparsevector »

btilly wrote: post #65
sparsevector wrote: post #63

Earlier quoted context omitted.

I think what you're describing is basically the non-stochastic setting. The idea there is to assume absolutely nothing about the rewards (they can be generated by quickly changing distributions or even an adversary) but still try to do as well as the best single arm. The standard algorithm for this problem is the multiplicative weights update method, also called the exponentially weighted average method or the hedge…

The article is interesting, but assumed you get to pull all of the arms at once, and see all of the results. That's different from the website optimization problem. The book looks like it would take a long time to work through, and they don't get to the multi-armed bandit problem until chapter 6. It goes into my todo list, but is likely to take a while to get off of it...

Yes, I realized after posting that this is probably a better paper to link to: http://cseweb.ucsd.edu/~yfreund/papers/bandits.pdf The algorithms for the partial information setting are sometimes surprisingly similar to the algorithms where you see all the results. The algorithm in the paper linked above is essentially the same algorithm but with a small exploration probability. The regret bound gets worse by a factor of sqrt(N), however.

Re: Why multi-armed bandit algorithm is not "better" than A/B testing

#69

Post by conductrics »

btilly wrote: post #50

(For previous discussion on this topic, see http://news.ycombinator.com/item?id=4040022. ) Let's stop a bad meme before it gets going. Multi-armed bandit is a general problem. There are many strategies for tackling it. An epsilon-greedy strategy is one strategy. It is not the only strategy, and it is not even a particularly good one. There are many others. In fact A/B testing is itself a solution to the multi-armed b…

This is a good coversation. So the Disclaimer, my company Conductrics.com allows you to use algos similar to bandits as well as AB/MVT.

AB can be thought of as more of a form of epoch- greedy - you play uniform random then play greedy. One advantage of e-greedy is that if your environment is not stationary - you are still sampling from the arms - its sort of an insurance premium. To address the differences in reward signals based on the environment, there is the option to model the environment with features - since it maybe that Fridays require a different selection than Sundays - not sure why you would a priori assume that the relative values, or even just the arm rankings are independent of environmental variables.

One other point- if you just want a super quick hack to pick winners (or at least pick from te set of higher performing arms) you can just optimistically seed your estimates for each arm - then just pick greedy. Not claiming it is optimal or anything but it requires almost no coding overhead. Of course you need the problem to be stationary.

Regardless of which algo approach you use, I do think it is useful to at least think in terms of bandits or reimforcemt learning when tackling these problems.

Re: Why multi-armed bandit algorithm is not "better" than A/B testing

#70

Post by sparsevector »

noelwelsh wrote: post #67
sparsevector wrote: post #63

Earlier quoted context omitted.

I think what you're describing is basically the non-stochastic setting. The idea there is to assume absolutely nothing about the rewards (they can be generated by quickly changing distributions or even an adversary) but still try to do as well as the best single arm. The standard algorithm for this problem is the multiplicative weights update method, also called the exponentially weighted average method or the hedge…

I don't think the non-stochastic setting is entirely appropriate. What we've been discussing is a situation where the differences in conversion rates are constant in expectation, though absolute conversion rates vary. So it's basically a stochastic setting, which should allow more leverage. Also, as I recall for the non-stochastic setting the definition of regret changes so the regret bounds are not directly comparab…

My take on btilly's problem was that the difference between the convergence rates is not constant but rather known to be bounded away from zero by some unknown constant. That is, there is some value epsilon such that the difference in conversion rate is on every round at least epsilon. However, at some rounds it could be more than epsilon, and it doesn't necessarily vary according to any fixed distribution. I think this is therefore roughly equivalent to the non stochastic setting additionally assuming the best arm has large (relative) reward.

I agree though that if the difference in conversion rate were stochastic that could potentially make the problem much easier.

Post reply on HN