5 ms·

Introduction to Multi-Armed Bandits (2019)

143 points by Anon84 1y ago

esafak 1y ago
One way to address the https://en.wikipedia.org/wiki/Exploration%E2%80%93exploitation_dilemma https://en.wikipedia.org/wiki/Exploration%E2%80%93exploitati...
rented_mule 1y ago
We 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 new set of options and arrive at a new optimal mix much more quickly. But we did want to run experiments with other things around the content that was managed by the bandits (e.g., UI flow, overall layout, other algorithmic things, etc.). It turns out bandits complicate these experiments significantly. Any changes to the context in which the bandits operate lead them to shift things more towards exploration to find a new optimal mix, hurting performance for some period of time. We had a choice we could make here... treat all traffic, regardless of cohort, as a single universe that the bandits are managing (so they would optimize for the mix of cohorts as a whole). Or we could setup bandit stats for each cohort. If things are combined, then we can't use an experiment design that assumes independence between cohorts (e.g., A/B testing) because the bandits break independence. But the optimal mix will likely look different for one cohort vs. another vs. all of them combined. So it's better for experiment validity to isolate the bandits for each cohort. Now small cohorts can take quite a while to converge before we can measure how well things work. All of this puts a real limit on iteration speed. 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. Much (all?) of this comes from bandits being feedback loops - these same problems are present in other approaches where feedback loops are used (e.g., control theory based approaches). Feedback mechanisms are incredibly powerful, but they couple things together in ways that can be difficult to tease apart.
- kianN 1y ago
  I’ve actually run into the exact same issue. At the time we similarly had to scrap bandits. Since then I’ve had the opportunity to do a fair amount of research into hierarchical dirichelete processes in an unrelated field. On a random day, a light went off in my head that hierarchy perfectly addresses the stratification vs aggregation problems that arise in bandits. Unfortunately I’ve never had a chance to apply this (and thus see the issues) in a relevant setting since.
  - CuriouslyC 1y ago
    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.
    - kianN 1y ago
      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?
      - CuriouslyC 1y ago
        I was using it for bioinformatics to incorporate measurement uncertainty from fluid microarrays into genotype cluster estimates.
  - hruk 1y ago
    You can do fairly well here with ridge regression as a poor man's hierarchical model. We've used this library's Bayesian ridge regression to support a geo-pricing strategy (and it contains the Dirichlet-Multinomial approach as well): https://github.com/bayesianbandits/bayesianbandits https://github.com/bayesianbandits/bayesianbandits
- dr_dshiv 1y ago
  “ If things are combined, then we can't use an experiment design that assumes independence between cohorts (e.g., A/B testing) because the bandits break independence.” Can you explain, please?
Normal_gaussian 1y ago
Its very easy to implement toy multi-armed bandits, and even getting them into production code isn't so bad. Its the reporting, education, and adding features without breaking everything that gets very hard very quick.
- 3abiton 1y ago
  > Its the reporting, education, and adding features without breaking everything that gets very hard very quick. What's challenging about that though?
  - taormina 1y ago
    I’ve found this all to be just as straightforward as implementing the MAB in my experience.
  - Normal_gaussian 1y ago
    mab's get misinterpreted very easily, particularly because they tend to be useful in places where the non-technical (or low stats knowledge) people are the major stakeholders. Reporting on MAB functionality and output inline with other features without overcomplicating interpretation or leading to easy misinterpretation is an often underestimated task. Then allowing iteration on this without breaking any of the careful presentation or decisions made is a challenge for any MoC process.
Brystephor 1y ago
Hey, an area I actually work on and use in production! MAB in our case has shown improvements in our A/B metrics. My general takeaways for my experience with MAB: * we have a single optimization goal (e.g the metric to minimize or maximize). The hard part isnt defining a optimization goal. The hard part is identifying what stakeholders actually want the tradeoff between different metrics. If you have goal A and goal B, where B is more aggressive than A, then getting agreement on which is better is hard. This is a people problem. * MAB seems to be a good proof of concept that something that can be optimized but isnt an "end game" optimization path. * MAB for A/B testing is going to mess up your AB data and make everything more difficult. You should have a treatment that uses the MAB algorithm and a treatment that doesnt. All of the above is for non contextual MAB. I am currently learning about different MAB algorithms although each of them are pretty similar. The ones ive read about are all effectively linear/logistic regression and tbe differences come from exploration mechanism and how uncertainty is represented. Epsilon greedy has no uncertainty, exploration just happens a fixed percentage of time. UCB is optimistic about uncertainty, and the amount of optimism controls exploration. Thompson sampling uses statistical (beta) distributions about uncertainty, exploration happens less as confidence about a particular set of options increases. Overall its a fun area to work in that is quite different from your typical CRUD development which is a nice change of pace.
- Iwan-Zotow 1y ago
  Do you have write ups how to use it in production?
  - Brystephor 1y ago
    No public write ups. What information would you want to see? I think there's two categories: infra ops info, and then product insights and "gotchas"/unintuitive but valid results.
jmward01 1y ago
I used bandits to select a best vendor/model to use on a per customer basis for a task that we had a reward signal for. It worked amazingly well but the more important thing we gained was the ability to accurately estimate the improvement other features/changes had. Getting a hard number for 'feature x improved over previous baseline by y' is a game changer for a lot of product and development work. You only think feature x is a massive improvement, until you see the numbers and realize that the spacing displayed to a user was 10x move valuable than the Really Big Feature you thought was going to make a difference.
BrenBarn 1y ago
Just from a philosophical perspective I think multi-armed bandits are a fascinating idea and a great technique for thinking about many kinds of decision processes.
praptak 1y ago
Multi-Armed Bandits running on move trees (aka the UCT algorithm) was the invention that led the foundation to computers cracking Go.
codeulike 1y ago
Does 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 https://en.wikipedia.org/wiki/Multi-armed_bandit
- PanoptesYC 1y ago
  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."
liampulles 1y ago
There 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 https://www.youtube.com/watch?v=sf0vb4yiZR4
- novaleaf 1y ago
  I'm only about 5 min into it, but wow. Excellent.
cdelsolar 1y ago
We use multi armed bandits in scrabble Montecarlo sims to smartly pick the best performing move.

143 points by Anon84 1y ago

One way to address the https://en.wikipedia.org/wiki/Exploration%E2%80%93exploitation_dilemma https://en.wikipedia.org/wiki/Exploration%E2%80%93exploitati...

rented_mule 1y ago

We 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 new set of options and arrive at a new optimal mix much more quickly. But we did want to run experiments with other things around the content that was managed by the bandits (e.g., UI flow, overall layout, other algorithmic things, etc.). It turns out bandits complicate these experiments significantly. Any changes to the context in which the bandits operate lead them to shift things more towards exploration to find a new optimal mix, hurting performance for some period of time. We had a choice we could make here... treat all traffic, regardless of cohort, as a single universe that the bandits are managing (so they would optimize for the mix of cohorts as a whole). Or we could setup bandit stats for each cohort. If things are combined, then we can't use an experiment design that assumes independence between cohorts (e.g., A/B testing) because the bandits break independence. But the optimal mix will likely look different for one cohort vs. another vs. all of them combined. So it's better for experiment validity to isolate the bandits for each cohort. Now small cohorts can take quite a while to converge before we can measure how well things work. All of this puts a real limit on iteration speed. 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. Much (all?) of this comes from bandits being feedback loops - these same problems are present in other approaches where feedback loops are used (e.g., control theory based approaches). Feedback mechanisms are incredibly powerful, but they couple things together in ways that can be difficult to tease apart.

kianN 1y ago
I’ve actually run into the exact same issue. At the time we similarly had to scrap bandits. Since then I’ve had the opportunity to do a fair amount of research into hierarchical dirichelete processes in an unrelated field. On a random day, a light went off in my head that hierarchy perfectly addresses the stratification vs aggregation problems that arise in bandits. Unfortunately I’ve never had a chance to apply this (and thus see the issues) in a relevant setting since.
- CuriouslyC 1y ago
  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.
  - kianN 1y ago
    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?
    - CuriouslyC 1y ago
      I was using it for bioinformatics to incorporate measurement uncertainty from fluid microarrays into genotype cluster estimates.
- hruk 1y ago
  You can do fairly well here with ridge regression as a poor man's hierarchical model. We've used this library's Bayesian ridge regression to support a geo-pricing strategy (and it contains the Dirichlet-Multinomial approach as well): https://github.com/bayesianbandits/bayesianbandits https://github.com/bayesianbandits/bayesianbandits
dr_dshiv 1y ago
“ If things are combined, then we can't use an experiment design that assumes independence between cohorts (e.g., A/B testing) because the bandits break independence.” Can you explain, please?

Normal_gaussian 1y ago

Its very easy to implement toy multi-armed bandits, and even getting them into production code isn't so bad. Its the reporting, education, and adding features without breaking everything that gets very hard very quick.

3abiton 1y ago
> Its the reporting, education, and adding features without breaking everything that gets very hard very quick. What's challenging about that though?
- taormina 1y ago
  I’ve found this all to be just as straightforward as implementing the MAB in my experience.
- Normal_gaussian 1y ago
  mab's get misinterpreted very easily, particularly because they tend to be useful in places where the non-technical (or low stats knowledge) people are the major stakeholders. Reporting on MAB functionality and output inline with other features without overcomplicating interpretation or leading to easy misinterpretation is an often underestimated task. Then allowing iteration on this without breaking any of the careful presentation or decisions made is a challenge for any MoC process.

Brystephor 1y ago

Hey, an area I actually work on and use in production! MAB in our case has shown improvements in our A/B metrics. My general takeaways for my experience with MAB: * we have a single optimization goal (e.g the metric to minimize or maximize). The hard part isnt defining a optimization goal. The hard part is identifying what stakeholders actually want the tradeoff between different metrics. If you have goal A and goal B, where B is more aggressive than A, then getting agreement on which is better is hard. This is a people problem. * MAB seems to be a good proof of concept that something that can be optimized but isnt an "end game" optimization path. * MAB for A/B testing is going to mess up your AB data and make everything more difficult. You should have a treatment that uses the MAB algorithm and a treatment that doesnt. All of the above is for non contextual MAB. I am currently learning about different MAB algorithms although each of them are pretty similar. The ones ive read about are all effectively linear/logistic regression and tbe differences come from exploration mechanism and how uncertainty is represented. Epsilon greedy has no uncertainty, exploration just happens a fixed percentage of time. UCB is optimistic about uncertainty, and the amount of optimism controls exploration. Thompson sampling uses statistical (beta) distributions about uncertainty, exploration happens less as confidence about a particular set of options increases. Overall its a fun area to work in that is quite different from your typical CRUD development which is a nice change of pace.

Iwan-Zotow 1y ago
Do you have write ups how to use it in production?
- Brystephor 1y ago
  No public write ups. What information would you want to see? I think there's two categories: infra ops info, and then product insights and "gotchas"/unintuitive but valid results.

jmward01 1y ago

I used bandits to select a best vendor/model to use on a per customer basis for a task that we had a reward signal for. It worked amazingly well but the more important thing we gained was the ability to accurately estimate the improvement other features/changes had. Getting a hard number for 'feature x improved over previous baseline by y' is a game changer for a lot of product and development work. You only think feature x is a massive improvement, until you see the numbers and realize that the spacing displayed to a user was 10x move valuable than the Really Big Feature you thought was going to make a difference.

BrenBarn 1y ago

Just from a philosophical perspective I think multi-armed bandits are a fascinating idea and a great technique for thinking about many kinds of decision processes.

praptak 1y ago

Multi-Armed Bandits running on move trees (aka the UCT algorithm) was the invention that led the foundation to computers cracking Go.

codeulike 1y ago

Does 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 https://en.wikipedia.org/wiki/Multi-armed_bandit

PanoptesYC 1y ago
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."

liampulles 1y ago

There 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 https://www.youtube.com/watch?v=sf0vb4yiZR4

novaleaf 1y ago
I'm only about 5 min into it, but wow. Excellent.

cdelsolar 1y ago

We use multi armed bandits in scrabble Montecarlo sims to smartly pick the best performing move.