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

The multi-armed bandit problem (2012)

stevehanov.ca

Post reply on HN
Print view View original

31–40 of 82 posts

Re: The multi-armed bandit problem (2012)

#31

Post by JohannesH »

err4nt wrote: post #25
citrablue wrote: post #18

Earlier quoted context omitted.

What you said is correct, but I'd like to point out that controlled scientific experiments may not be the right approach for e.g. optimizing conversions on a website. The reason is that websites are a dynamic environment. All things equal, better controlled experiments are great. However, visitor behavior, especially when from dynamic sources (google serps change weekly), changes all the time. And that's why I prefer…

> Does anyone go back and re-test their biggest wins? Yes, absolutely! We do research first, then come up with simple, well-controlled tests. Once we have a winner we can either lock it in, but often we continue to research and experiment on the new knowledge we gained. A hefty minority of the tests I implement build on past wins to further flesh out what works and what doesn't with knowledge and the data to back it…

Very interesting. It seems to me that doing incremental work like this might end up in a local minima/maxima. Do you have any advice on how to avoid pitfalls like that? Are you testing radically different ideas along with your incremental improvements?

Re: The multi-armed bandit problem (2012)

#32

Post by edmundsauto »

err4nt wrote: post #25
citrablue wrote: post #18

Earlier quoted context omitted.

What you said is correct, but I'd like to point out that controlled scientific experiments may not be the right approach for e.g. optimizing conversions on a website. The reason is that websites are a dynamic environment. All things equal, better controlled experiments are great. However, visitor behavior, especially when from dynamic sources (google serps change weekly), changes all the time. And that's why I prefer…

> Does anyone go back and re-test their biggest wins? Yes, absolutely! We do research first, then come up with simple, well-controlled tests. Once we have a winner we can either lock it in, but often we continue to research and experiment on the new knowledge we gained. A hefty minority of the tests I implement build on past wins to further flesh out what works and what doesn't with knowledge and the data to back it…

How do you do knowledge transfer when you're documenting what you've learned? I have found even simple changes often don't reproduce on the same site. It feels like a easy trap for an expert practitioner to fall into -- the belief they can predict the outcome of a test based on a different test they ran.

Sometimes, yes, but often it's not for the reasons people think. This seems very much in Danny Kahneman land -- we can't trust what our brain is telling us, that this experience will have similar results in this other context.

I recently worked at a place that ran > 20 websites, huge traffic numbers, with around 100 simultaneous tests. We would poll each employee about their guess for the test winner. The results were about on par with everyone randomly guessing.

Re: The multi-armed bandit problem (2012)

#33

Post by nestorD »

j2kun wrote: post #30

UCB1 is really not that much more complicated than epsilon-greedy. Some slightly sloppy code I wrote a few years ago, maybe 20 lines of code: https://github.com/j2kun/ucb1/blob/master/ucb1.py#L7-L35 Sure you have to read a bit more to know why it works, but if you write your code well you could plug this in without any extra trouble. It's not like you need a special optimization solver as a dependency.

And, for not much more effort (computing the variance of your samples), you can use UCB1-tuned [0] which gets rid of the 'c' parameter and tends to be even better.

I personnaly think that it should replace UCB1 as a baseline when trying bandit algorithms.

[0]: https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf

Re: The multi-armed bandit problem (2012)

#34

Post by 60654 »

Multi-armed bandits are also well known in game AI. They got popular with the introduction of Monte Carlo Tree Search, where MAB are used there to select which subtrees to search for largest expected payoff, e.g.:

https://www.aaai.org/ocs/index.php/AIIDE/AIIDE13/paper/view/... https://courses.cs.washington.edu/courses/cse599i/18wi/resou... etc.

For what it's worth the MAB algo in the original post looks like Epsilon Greedy. It's probably better to look into Upper Confidence Bound variants like UCB1 that dynamically adjust how much to explore vs exploit, e.g.:

https://towardsdatascience.com/comparing-multi-armed-bandit-...

Re: The multi-armed bandit problem (2012)

#35

Post by edmundsauto »

elehack wrote: post #14
err4nt wrote: post #9

The purpose of an A/B test isn't to always show the best performing result, it's to perform a _controlled scientific experiment_ with a control group, from which you can learn things. Also, I work in this field and I will just say that people _do_ behave differently based on traffic source: i.e. users coming from Facebook behave alike, but different than traffic from Reddit who act similarly to each other. If you wer…

Yes. Bandits will often converge more quickly to the optimal strategy, but it is much more difficult to understand why that strategy is optimal and generalize from the bandit outcomes to predict future performance and performance of other strategies. It isn't impossible - bandits are seeing adoption in medical trials to avoid precisely the problem discussed - but the standard experiment design and analysis techniques…

But for results to generalize or to understand why, the confounders must be accounted for in the randomization. This is really hard to do well -- there are often subtle influences that aren't sufficiently understood how they impact these non-linear systems. What makes someone convert? A million different factors; changing the color of a button in one context doesn't necessarily tell me much about how people would respond to that experience in another context.

It's easy to underestimate how complex things are, because we only see some superficial aspects of e.g. a user/software interaction model. This flaw is down to how our brains work -- ref "What you see is all there is".

Re: The multi-armed bandit problem (2012)

#36

Post by lowdose »

Microsoft had good talk about contextual bandits and machine learning. The business case discussed was webpage conversion optimization which increased by 80%.

https://www.microsoft.com/en-us/research/blog/new-perspectiv...

https://podcasts.apple.com/nl/podcast/microsoft-research-pod...

Re: The multi-armed bandit problem (2012)

#37

Post by 60654 »

nestorD wrote: post #33
j2kun wrote: post #30

UCB1 is really not that much more complicated than epsilon-greedy. Some slightly sloppy code I wrote a few years ago, maybe 20 lines of code: https://github.com/j2kun/ucb1/blob/master/ucb1.py#L7-L35 Sure you have to read a bit more to know why it works, but if you write your code well you could plug this in without any extra trouble. It's not like you need a special optimization solver as a dependency.

And, for not much more effort (computing the variance of your samples), you can use UCB1-tuned [0] which gets rid of the 'c' parameter and tends to be even better. I personnaly think that it should replace UCB1 as a baseline when trying bandit algorithms. [0]: https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf

That's a nice paper, thanks for posting this!

Re: The multi-armed bandit problem (2012)

#38

Post by edmundsauto »

comicjk wrote: post #22
orasis wrote: post #19

Earlier quoted context omitted.

I disagree. I’ve spent a lot of time staring at bandit outcomes and usually they match some sort of intuition of why a variant might be exceptional.

That could be post-hoc reasoning, though. It would be interesting to pre-register your hypotheses, or see whether you could tell bandit outcomes from random ones.

Isn't this problem also an issue when people talk about transferring what they learn from one test to another test? That is frequently cited as a benefit of A/B testing.

Re: The multi-armed bandit problem (2012)

#39

Post by opportune »

daenz wrote: post #8

It seems close to simulated annealing in the travelling salesman problem. The basics of it is that you start with a random tour and adjust path segments incrementally. Most of the time, you choose a new path segment that decreases the global route cost, but randomly, you choose a new path segment that increases the global route cost. This random factor is decreased over time, so the route anneals and settles on a clo…

Basically you are comparing one strategy to prevent local optima in one optimization algorithm to another strategy in a different optimization algorithm. There are such strategies for basically every optimization problem.

Other examples: momentum in deep learning, tabu search, random search, etc.

The benefit of doing a pure binary A/B test is that the experiment is so simple that as long as you don't break the cardinal rules (you need a fixed experiment size! Most people don't even do this. Also you need to not bias your control/experiment sets) it is easy to get statistically valid results. When doing multivariate optimization using something that is measured (such as user engagement) rather than evaluated, you need a good amount of data for each configuration to evaluate it, or you run the risk of optimizing for random noise. This is true of even the multi-armed bandit problem: if you vary the exploitation strategies over time, then confounding temporal variables (for example, purchases are higher on weekdays because that's when people make business decisions at work) can invalidate the experiment if not controlled for.

Re: The multi-armed bandit problem (2012)

#40

Post by opportune »

comicjk wrote: post #24
a13n wrote: post #6

Also one reason a lot of teams can't do more than two options (A, B, C, D, E, F, G, etc. testing) is because you need a TON of traffic for it to be statistically significant.

Statistical significance isn't necessary for deriving value from information! The point of multi-armed bandit is that you use the best information you currently have, while also not taking that information too seriously. In a context where experiments have a cost and you need results, this makes more sense than gathering more and more data until you meet statistical significance thresholds.

If random noise is more likely to explain the validity of one hypothesis over another, then your information has very little value.
Post reply on HN