# Multi-armed bandit algorithms vs Uplift modeling

Multi-Armed Bandit: http://en.wikipedia.org/wiki/Multi-armed_bandit

Uplift Modeling: http://en.wikipedia.org/wiki/Uplift_modelling

How are these two approaches different? How are they similar? Is one better than the other?

Edit: If an example scenario is needed, consider the following. We're placing banner ads online and want to target the right people. Basically, those people who if presented with the ad are more likely to take a desired action. This sounds like an Uplift Model problem but I'm not sure if armed bandit is also applicable in this case.

Almost five months with no answer! Here's how I understand it: uplift models use results gathered from a randomized control experiment to better choose targets for the next cycle. Multi-armed bandit problems don't have control and experiment groups. Instead, they're a problem of online learning, where you switch between different treatments on the fly.

TL;DR
Both approaches address the general problem of choosing an optimal treatment.

Uplift models can be flexibly used with all state-of-the-art ML models, e.g. tree-based learners, and provide an interpretable estimate of the treatment effect on a customer.
Uplift models are difficult to apply when there are more than a few treatment options, because we conduct a randomized experiment collecting data on each potential treatment. Imagine, for example, not four coupon values but 1000 banner designs.

Contextual bandit algorithms also model treatment outcome for the customer, but conduct the experiment one observation at a time and focus on treatments that are profitable or yet underexplored. The focus allows them to deal with a large number of treatments, but often requires an estimate of model uncertainty and online updating, so analysis and deployment are different from the standard ML pipeline.

Effect estimation vs. decision optimization
Uplift modeling and Bandit algorithms are both approaches to investigate the causal effect of treatment, but their original applications differ.

Uplift-type models come from the medical and econometric literature with the original application to estimate the average and later estimate the conditional average treatment effect (2), by conducting a randomized experimental study (3) with a small number of treatments (1). While the goal of much of the literature is the accurate estimation of the treatment effect, the 'uplift' stream uses the same methods to inform the customer targeting decision and target those with high treatment 'scores'.

Bandit algorithms come from the computer science and optimization literature and are a type of reinforcement learning. The original application to choose between actions (2), when there might many possible actions (1) by exploring their outcomes efficiently through repeated trials (3) with the goal to identify the most profitable action after as few suboptimal decisions as possible.
Basic bandit algorithms search actions that are profitable on average and ignore customer attributes, but contextual bandits model the outcome conditional on the customer.

1) Number of treatments/actions
Bandit algorithms are, at least in principle, designed to work on a large action space, e.g. hundreds of potential banners. We expect them to disregard unprofitable actions quickly and focus on few profitable actions during experimentation.

Uplift models use a random sample of observations under each treatment to estimate its effect compared to other treatments or the control group. We would, for example, collect the outcomes for 5000 customers per available banner. The experiment becomes huge if we show each of hundreds of banners to random 5000 customers. Nevertheless, when applicable uplift models are stable and treatment estimates have nice statistical properties.

2) Interpretation of the estimate
Uplift models predict the effect of the treatment on a customer, e.g. how much more would that customer spend if we would show him this ad banner. This prediction could be the goal of the investigation, but is typically used to do a cost-benefit analysis and target customers for whom the incremental revenue outweights the offer cost.

Bandit algorithms are focused on the decision-problem directly. I believe some common methods do allow interpretation of the estimated effect (e.g. linUCB) but the predicted score of policy gradient methods is hard to analyze.

3) Data collection
The data used for uplift modeling is collected in a randomized experiment, where N customers see one of the banners at random. Whenever we want to reestimate the model, we will need to run another experiment.

Bandit algorithms collect data actively in a setting where customers are evaluated one-by-one. The treatment assignment is not randomized, but based on current estimates. Typically, bandit algorithms will play treatments with high expected outcome and treatments for which the outcome is uncertain. Conversely, they stop playing treatments with certain, low outcomes. The necessity of an estimate of the uncertainty is one thing that makes the design of bandit algorithms difficult.

In principle, bandit algorithms are designed to work by assigning treatment, then observing the outcome, then updating the model before the next prediction. Model updating can be done in batch after collecting some observations, but online training is a big part of the decision optimization. Online training is another thing that makes the design and deployment more difficult.