Stochastic multi-armed bandit problem with transition costs The stochastic multi-armed bandit problem ($k$ arms, the $i$'th of which gives you a reward of $1$ with unknown probability $p_i$, and $0$ with probability $1-p_i$, and you must decide at each stage which arm to pull based on the past reward history) is well-studied. For example, there is the UCB1 algorithm of Auer, Cesa-Bianchi, and Fisher which achieves expected regret of $O(\log n)$ in $n$ iterations, treating the other parameters ($k$ and the probabilities $p_i$) as fixed. 

My question is: is there any literature out there on this problem with transition costs?  Namely, suppose you pay a cost of $P(i,j)$ whenever you pull arm $j$ immediately after pulling arm $i$? 

Thank you!
Yes, it's been studied -- for example you can look at this survey, which is from the econ community.

Also, [Auer '02] considered a similar problem, which he called "shifting bandits" where the learner has to compete with the optimal policy that's allowed to make $s$ shifts, in the adversarial setting -- see section 3 of this paper.