Understanding a bandit

A multi-armed bandit problem involves making a choice in the face of complete uncertainty. More specifically, imagine you're placed in front of several slot machines, and each has a different but fixed probability to pay out. How could you make as much money as possible?

So, this is a metaphor for the problem. It really applies to any situation where you have no information to start with, and where you stand to gain something.

There are two concepts that are critical in understanding algorithms that solve this class of problem: exploration and exploitation. Exploration refers to the algorithm choosing to play a strategy to gain more information about the given strategy. Exploitation is what happens when the algorithm decides to try the currently winning strategy in an effort to maximize the pay off. A great concrete example of this is split testing (or A/B testing), which is a feature on a website. Imagine an algorithm that only ever chooses the current best-performing...