Multi-armed bandits with simple arms

Abstract

An exact solution to certain multi-armed bandit problems with independent and simple arms is presented. An arm is simple if the observations associated with the arm have one of two distributions conditional on the value of an unknown dichotomous parameter. This solution is obtained relating Gittins indices for the arms to ladder variables for associated random walks.