Multi-Armed Bandits running on move trees (aka the UCT algorithm) was the invention that led the foundation to computers cracking Go.
Introduction to Multi-Armed Bandits (2019)
21–30 of 34 posts
Re: Introduction to Multi-Armed Bandits (2019)
#22Does the name "Multi-Armed Bandits" have anything to do with "One Armed Bandits" - old style slot machine/fruit machines/gambling machines with a big lever that people would pull?
edit: ah ok yes it does: https://en.wikipedia.org/wiki/Multi-armed_bandit
Re: Introduction to Multi-Armed Bandits (2019)
#23We employed bandits in a product I worked on. It was selecting which piece of content to show in a certain context, optimizing for clicks. It did a great job, but there were implications that I wish we understood from the start. There was a constant stream of new content (i.e., arms for the bandits) to choose from. Instead of running manual experiments (e.g., A/B tests or other designs), the bandits would sample the…
>Things also become very difficult to reason about because their is state in the bandit stats that are being used to optimize things. You can often think of that as a black box, but sometimes you need to look inside and it can be very difficult.
One way to peak into the state is to use bayesian models to represent the "belief" state of the bandits. For example, the arm's "utility" can be a linear function of the features of the arm. At each period, you can inspect the coefficients (and their distribution) for each arm.
See this package:
Re: Introduction to Multi-Armed Bandits (2019)
#24We employed bandits in a product I worked on. It was selecting which piece of content to show in a certain context, optimizing for clicks. It did a great job, but there were implications that I wish we understood from the start. There was a constant stream of new content (i.e., arms for the bandits) to choose from. Instead of running manual experiments (e.g., A/B tests or other designs), the bandits would sample the…
The real trouble with bandits is that people don't bother to look into what the real potential benefit is as far as the target you're optimizing. Despite theoretically loving bandit techniques, I've convinced multiple teams not to go that path because the real advantage of using them is a slightly more optimal mix of people in experiment than if you ran them manually. At some scales it can make sense, but for the vas…
Thanks for the inputs.
"Bandits work best for relatively simple optimization choices at very large scale"
Have you considered different methods to address this shortcoming?
Re: Introduction to Multi-Armed Bandits (2019)
#25There is a great video with Jim Manzi on the subject of applying experiments in a business/government context - I think people interested in the subject might enjoy it:
Re: Introduction to Multi-Armed Bandits (2019)
#26Does the name "Multi-Armed Bandits" have anything to do with "One Armed Bandits" - old style slot machine/fruit machines/gambling machines with a big lever that people would pull? edit: ah ok yes it does: https://en.wikipedia.org/wiki/Multi-armed_bandit
Yes. The paper explains the basic model as so:
"We consider the basic model with IID rewards, called stochastic bandits. An algorithm has K possible actions to choose from, a.k.a. arms, and there are T rounds, for some known K and T . In each round, the algorithm chooses an arm and collects a reward for this arm. The algorithm’s goal is to maximize its total reward over the T rounds."
Re: Introduction to Multi-Armed Bandits (2019)
#27Earlier quoted context omitted.
The real trouble with bandits is that people don't bother to look into what the real potential benefit is as far as the target you're optimizing. Despite theoretically loving bandit techniques, I've convinced multiple teams not to go that path because the real advantage of using them is a slightly more optimal mix of people in experiment than if you ran them manually. At some scales it can make sense, but for the vas…
Thanks for the inputs. "Bandits work best for relatively simple optimization choices at very large scale" Have you considered different methods to address this shortcoming?
This is basically Breiman's "two cultures" at play. Do you care about optimizing y-hat, or do you care about doing inference on some parameters in your model? Depends on the business case, typically.
Re: Introduction to Multi-Armed Bandits (2019)
#28There is a great video with Jim Manzi on the subject of applying experiments in a business/government context - I think people interested in the subject might enjoy it: https://www.youtube.com/watch?v=sf0vb4yiZR4
I'm only about 5 min into it, but wow. Excellent.
Re: Introduction to Multi-Armed Bandits (2019)
#29We use multi armed bandits in scrabble Montecarlo sims to smartly pick the best performing move.
Re: Introduction to Multi-Armed Bandits (2019)
#30Earlier quoted context omitted.
Ahh, hierarchical dirichlet processes. Sounds like you were reading the literature on Bayesian diffusion modelling / diffusion trees. I studied that stuff almost 20 years ago now, really takes me back.
Haha I’ve actually never heard of that field. My work was focused on applying Chinese restaurant process models to text analysis. But very curious what you were working on?
I was using it for bioinformatics to incorporate measurement uncertainty from fluid microarrays into genotype cluster estimates.