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

Introduction to Multi-Armed Bandits (2019)

arxiv.org

Post reply on HN
Print view View original

11–20 of 34 posts

Re: Introduction to Multi-Armed Bandits (2019)

#11

Post by crystal_revenge »

rented_mule wrote: post #3

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…

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 vast majority of products/companies the statistical benefits don't outweigh the added complexity.

Bandits work best for relatively simple optimization choices at very large scale. If you care at all about the information gained in an experiment, it's fairly unlikely bandits are a good choice for you (or any reinforcement learning algorithm at that point).

Re: Introduction to Multi-Armed Bandits (2019)

#12

Post by kianN »

CuriouslyC wrote: post #7
kianN wrote: post #4

Earlier quoted context omitted.

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…

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?

Re: Introduction to Multi-Armed Bandits (2019)

#13

Post by rented_mule »

hervature wrote: post #6
dr_dshiv wrote: post #5

Earlier quoted context omitted.

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

Not the OP. I think what they are driving at is that if knowledge is discovered during exploration in cohort A, cohort B can exploit it. Then, the whole A/B test breaks down to which cohort got to benefit more from the bandit learnings.

Yes, this is exactly the kind of scenario I was alluding to.

For example, cohorts with very light traffic are likely to get undue benefit as a lot of exploration might be done before the smaller cohort needs to select an arm, so things are closer to convergence.

Another example is if there are wildly different outcomes between cohorts. More of the exploration will be done in cohorts with more traffic, leading bandit optimizations to fit large cohorts better than lower traffic cohorts.

Even if you do manage to make things independent, you have to wait for bandit convergence before you know what converged results will look like. That requires being able to measure convergence, which isn't always easy, especially if you don't know to do that before designing the system.

With all of these problems, we kept bandits, and even expanded their application. At least for the 10 years I was still around. They are incredibly powerful. But there was a lot of "I wish those damned bandits didn't work so well!"

For anyone who is not aware, A/B tests assume cohorts behave independently of each other. The less true that is, the less reliable the results are. This was even worse for us in parts of our system where there were no bandits, but there was direct interactions between individuals.

Re: Introduction to Multi-Armed Bandits (2019)

#14

Post by rented_mule »

crystal_revenge wrote: post #11
rented_mule wrote: post #3

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…

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…

Agreed. In the case I was describing above, new arms were constantly being introduced (often several times a day for each of hundreds of thousands of scenarios). Manual experiments weren't an option. This also meant we were in a constant state of partial convergence for most scenarios, but the same would be true with experiments.

How to cull arms, so that there are enough samples for any kind of convergence, is another problem in this setup. We eventually built an ML model to select arms and used bandits to pick between them. This proved "too effective". The arms were all user-generated content. The bandits on top of the model, both setup to maximize clicks was stupidly good at surfacing inappropriate content because it got a lot of clicks. We ended up having to put more safeties on arm selection for certain categories of our content where we had the most inappropriate submissions.

Re: Introduction to Multi-Armed Bandits (2019)

#15

Post by Brystephor »

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.

Re: Introduction to Multi-Armed Bandits (2019)

#16

Post by BOOSTERHIDROGEN »

rented_mule wrote: post #3

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…

Could you expand on control theory? Is it PID?

Re: Introduction to Multi-Armed Bandits (2019)

#17

Post by jmward01 »

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.

Re: Introduction to Multi-Armed Bandits (2019)

#19

Post by taormina »

3abiton wrote: post #10
Normal_gaussian wrote: post #9

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.

> Its the reporting, education, and adding features without breaking everything that gets very hard very quick. What's challenging about that though?

I’ve found this all to be just as straightforward as implementing the MAB in my experience.

Re: Introduction to Multi-Armed Bandits (2019)

#20

Post by rented_mule »

BOOSTERHIDROGEN wrote: post #16
rented_mule wrote: post #3

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…

Could you expand on control theory? Is it PID?

I was just mentioning that any feedback loops have the potential downside of coupling things together in ways that make experiments (and analysis, improvements, etc.) difficult.

I used control theory as an example of another type of feedback loop because we were using controllers in other parts of the system. One was roughly the proportional term of a PID controller. Another was both the proportional and integral terms, but with a lot of domain specific heuristics added on (e.g., ML models to set baselines that help the controllers understand how quickly to move values). This was all incredibly powerful, but also required experiment design and analysis that was far more complicated than we would have liked.

This was not a ride-sharing company, but you can imagine dynamic pricing for Uber or Lyft working this way. Use a controller to try to keep the number of available riders and drivers in balance. If riders exceed drivers, increase payment to drivers (and therefore cost to riders), thereby attracting more riders. If drivers are sitting idle, decrease payment. Ideally, this is done constantly to respond to time of day, weather, traffic, etc. (with some predictive baseline expectations to keep it from being too slow to respond). When you get it right, riders get the cheapest price that ensures a driver is available. In economic terminology, this is finding the market clearing price. A controller can get you a long way in a hurry on such a system. But it's certainly not the only approach that can work, and it takes a lot to get it right (I have no idea how Uber and Lyft actually do any of this).

Post reply on HN