  We study the multi-armed bandit problem with arms which are Markov chains
with rewards. In the finite-horizon setting, the celebrated Gittins indices do
not apply, and the exact solution is intractable. We provide approximation
algorithms for a more general model which includes Markov decision processes
and non-unit transition times. When preemption is allowed, we provide a
(1/2-eps)-approximation, along with an example showing this is tight. When
preemption isn't allowed, we provide a 1/12-approximation, which improves to a
4/27-approximation when transition times are unity. Our model encompasses the
Markovian Bandits model of Gupta et al, the Stochastic Knapsack model of Dean,
Goemans, and Vondrak, and the Budgeted Learning model of Guha and Munagala, and
our algorithms improve existing results in all three areas. In our analysis, we
encounter and overcome to our knowledge a novel obstacle - an algorithm that
provably exists via polyhedral arguments, but cannot be found in polynomial
time.
