An Introduction to Reinforcement Learning: the K-Armed Bandit

Ever since DeepMind published its paper "Playing Atari with Deep Reinforcement Learning", many promising results have come out, with perhaps the most famous one being AlphaGo. Before we can understand how these models work, however, we need to understand some basic principles of reinforcement learning. I think the best introduction to these concepts is through a much simpler problem -- the so-called "k-armed bandit problem". First, let's define what the k-armed bandit problem is. The phrase "k-armed bandit" conjures up images of Boba Fett from Star Wars crossed with an octopus, but fortunately things are not that crazy.