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

51–60 of 82 posts

Re: The multi-armed bandit problem (2012)

#51

Post by praptak »

60654 wrote: post #34

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…

UCB on game trees (MCTS) was the first breakthrough that created decently playing Go programs, if I remember correctly.

Re: The multi-armed bandit problem (2012)

#52

Post by orasis »

JohannesH wrote: post #31
err4nt wrote: post #25

Earlier quoted context omitted.

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

From a workflow perspective, MAB is a bit difficult to find radical improvements from. The radical improvements come from fundamental design changes, of which it would be very expensive to create a bunch of radically different variants.

MAB is best used where you can generate a bunch of variants cheaply and hope for a 30% gain.

Re: The multi-armed bandit problem (2012)

#53

Post by orasis »

throwawaymath wrote: post #49
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…

> 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. Out of curiosity, what is your hypothesis for explaining this difference in behavior? Would you say it's primarily due to differing contexts in which a link is posted, or differing populations…

Different demographics, different intent, and different mental context all play a factor.

Re: The multi-armed bandit problem (2012)

#55

Post by ermik »

mhoad wrote: post #5

Previous discussions worth checking out here https://news.ycombinator.com/item?id=11437114 and here https://news.ycombinator.com/item?id=4040022

Besides the tree of these and those comments, do you have any other links to relevant subjects/writings?

Re: The multi-armed bandit problem (2012)

#56

Post by cgearhart »

praptak wrote: post #51
60654 wrote: post #34

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…

UCB on game trees (MCTS) was the first breakthrough that created decently playing Go programs, if I remember correctly.

You are correct. MCTS + UCB and other variants were state of the art leading up to AlphaGo. And even then, MCTS was also used in AlphaGo.

The main change in AlphaGo was using a deep learning network to encode a value network for fast rollouts and a policy network for move selection (rather than using the UCB rule). They later removed the value network and rollouts entirely, but even AlphaZero uses MCTS.

Re: The multi-armed bandit problem (2012)

#57

Post by moultano »

Does anyone have a reference for solving multi-armed bandit problems with a finite time horizon? I would like something that derives rules or heuristics for how your explore/exploit tradeoff changes as the horizon approaches.

This seems like an obvious extension, and something that someone should have worked on given how long this problem has been around, but I've been unable to find anything on it. Any pointers?

Re: The multi-armed bandit problem (2012)

#58

Post by ineedasername »

XCSme wrote: post #29

Just a small nitpick: this doesn't take into account implementation cost. If you want something dynamic like this it means your app has read access to all the analytics recorded (or at least the ones needed for optimization). Most of the times apps only send data to the analytics services, developers read/analyze them and act based on the data. I personally didn't work on any apps that were using analytics read acces…

Good point, the article says "do it in 20 lines of code", but implementation at scale may require a little more engineering than that.

Re: The multi-armed bandit problem (2012)

#59

Post by parksy »

orasis wrote: post #53
throwawaymath wrote: post #49

Earlier quoted context omitted.

> 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. Out of curiosity, what is your hypothesis for explaining this difference in behavior? Would you say it's primarily due to differing contexts in which a link is posted, or differing populations…

Different demographics, different intent, and different mental context all play a factor.

Not a statistician by any means, but could traffic source be a factor that's evaluated alongside conversion by a bandit algorithm when calculating the chance to show a particular option? Or other factors as well (detected device capabilities, users location, etc?)

These could just be weighting factors so instead of a single % chance per option, every time there's a successful interaction the victory is spread across the factors for that option.

New users could be shown the option where the chance for each option is weighted by the factors they match. Is this a valid approach or would it introduce some kind of selection bias?

Post reply on HN