6
$\begingroup$

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!

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.