Testing Multi-Arm Bandits on Historical Data

Suppose I want to test a multi-arm bandit algorithm in the contextual setting on a set of historical data. For simplicity, let's assume there are only two arms A and B and suppose the rewards are binary. Furthermore, suppose I have a data set where users were shown one of the two arms and I have a record of the rewards. What would be the best approach to simulating the scenario of running the algorithm online?

I was thinking of doing the following: If the algorithm outputs A then I want to record a reward so the algorithm can learn, to do this we sample uniformly at random from the set of data where users were shown the output to obtain this reward.

I'd like to know if this approach is suitable and if anyone knows of any better ways to simulate online learning algorithms with historical data, in particular the multi-arm bandit problem?

The problem you have is that the users were originally shown A or B under a different policy to that which the optimiser is learning. You probably don't know the probabilities for A or B from that policy (if you do, that would allow for a bit more subtlety).

You will need to reject samples that do not match what the optimiser does at any point. This may leave you with far less historical data to mine, and the possibility of getting a biased result.

to do this we sample uniformly at random from the set of data where users were shown the output to obtain this reward.

If I understand this correctly, you are planning to:

1. Pick an event (including user data) for input context
2. Generate the choice of A or B using your learning agent
3. Find another user that was presented the same output in the historical data, by sampling randomly from "all users shown A" or "all users shown B"
4. Count the reward generated in the sampled historical record

Sadly this will not work, because in step 3 you divorce the context from the agent's decision. So you will not be measuring the agent's likely reward, but the hybrid reward of an agent that uses a different user population and gains rewards according to the historic policies (which you may not even know).

A less biased approach might be:

1. Pick an event (including user data) randomly from historic data
2. Generate the choice of A or B using your learning agent
3. If the agent's choice and historic choice for that event match, then count the reward, else discard the event from the test

You may get sampling bias issues here if the agent's policy is different to historic policy for large number of users. The problem is that you are systematically removing users where old policies said one thing and new policies another, due to lack of data about the reward. So unless the original policy was completely random, the samples you actually train/evaluate on will not be chosen with correct ratios across the user population as it varies. Importance sampling could help mitigate that, but only if you know the probabilities of making A|B selection in both historic and learning agent policies.

Another possibility is to train a supervised model that predicts reward given user data and action from your historic data, and use that to drive a simulator of the online environment. If you are also training your agent during this test, you may need to simulate variance - e.g. turn probability of a click-through event into either a click or no click event by sampling $x < p(click)$ - because that is the data you need your online algorithm to learn from. This is clearly limited by the accuracy of the supervised model from the training data, but could reduce variance, because you will get some kind of indication of reward for events that did not happen historically (with some bounds on accuracy that you can estimate). That is due to function approximation in the supervised model - it is pretty similar idea to bootstrapping the Critic evaluation in an Actor-Critic reinforcement learning model.

• @Niel Slater how about using this approach arxiv.org/pdf/1003.5956.pdf – Pavan Sangha Jan 4 '18 at 14:47
• @PavanSangha: It looks to be better than my answer, although their theory initially assumes "the logging policy chose each arm at each time step uniformly at random" which I also cover by stating "So unless the original policy was completely random, your sample will not be even across the user population". However, their idea is tested in the paper, so go with that. Maybe write it up as a new answer if you think it works well, because the question is well received. – Neil Slater Jan 4 '18 at 14:52
• @Niel Slate thanks! If i was to know the policy used to recommend how would that change the problem in terms of simulation? – Pavan Sangha Jan 4 '18 at 15:26
• @PavanSangha You could then maybe use Importance Sampling - en.wikipedia.org/wiki/Importance_sampling - to weight each example according to the probability that you would make the same action choice comparing current agent with older policy. This only works if the old policy was stochastic (e.g. if it was greedy this could not work). Doing this removes selection bias, at the expense of adding variance. You can further use Weighted Importance Sampling to reduce the variance back down (and introduce a more manageable bias), but that is more complex as you need to estimate density. – Neil Slater Jan 4 '18 at 15:57
• @Niel Slater thanks for all the help, i have many more questions i'd love to ask you, could you create a chat room to discuss them? – Pavan Sangha Jan 4 '18 at 16:16