The multi-armed bandit problem (2012)
stevehanov.ca
The multi-armed bandit problem (2012)
1–10 of 82 posts
Re: The multi-armed bandit problem (2012)
#2Multi armed bandit algorithms have been used forever to optimize ads, websites, newsletters etc.
Here is an article from 2013 that describes Googles Multi Armed Bandits algo integration into Adsense:
https://www.cmswire.com/cms/customer-experience/google-integ...
The first time I stumbled across the term "Multi Armed Bandit" was when I read Koza's "On the programming of computers by natural selection" in 1992. When I later got involved in e-commerce projects, it was immediately clear to me that this was the way to tackle the involved optimization tasks.
Re: The multi-armed bandit problem (2012)
#3Multi armed bandit algorithms have been used forever to optimize ads, websites, newsletters etc. Here is an article from 2013 that describes Googles Multi Armed Bandits algo integration into Adsense: https://www.cmswire.com/cms/customer-experience/google-integ... The first time I stumbled across the term "Multi Armed Bandit" was when I read Koza's "On the programming of computers by natural selection" in 1992. When I…
OP itself says 'posted six years ago', so should probably have a (2013) - or thereabouts - in the submission title.
Re: The multi-armed bandit problem (2012)
#4Ahhh, the epsilon greedy strategy... I forgot I had read this until I was a few paragraphs in. If you have rare positive results, it gives you better statistics on your highest signal tests, while still evaluating the others (i.e. more than one alternative).
Re: The multi-armed bandit problem (2012)
#5Previous discussions worth checking out here https://news.ycombinator.com/item?id=11437114
Re: The multi-armed bandit problem (2012)
#6Also 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.
Re: The multi-armed bandit problem (2012)
#7At least for us, most A/B/.. tests require a stable assignment of test to user as key metrics like retention would obviously skewed by randomly assigning on each visit/page view.
Re: The multi-armed bandit problem (2012)
#8It 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 close-to-optimal result.
It shares the same principle of choosing reasonable options most of the time, but allowing variation to keep from getting stuck in a local optimum.
Re: The multi-armed bandit problem (2012)
#9The 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 were running a self-optimizing thing like this it _would_ make sense to split it up by the different traffic sources and handle them separately.
Re: The multi-armed bandit problem (2012)
#10At least for us, most A/B/.. tests require a stable assignment of test to user as key metrics like retention would obviously skewed by randomly assigning on each visit/page view.
The user id can be used to seed the random number algorithm to achieve that.