<p>Yes, it's been studied -- for example you can look at <a href="http://gandalf.psych.umn.edu/groups/schraterlab/papers/A_Survey_On_MABSC.pdf" rel="nofollow">this survey</a>, which is from the econ community.</p>

<p>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 <a href="http://jmlr.csail.mit.edu/papers/volume3/auer02a/auer02a.pdf" rel="nofollow">this paper</a>.</p>

CC BY-SA 2.5
2011-01-14T14:22:50.503Z
2011-01-14T15:07:11.227Z
2011-01-14T15:07:11.227Z
Lev Reyzin
<p>The stochastic multi-armed bandit problem ($k$ arms, the $i$'th of which gives you a reward of $1$ with <em>unknown</em> 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 <a href="http://www.eecs.berkeley.edu/~pabbeel/cs287-fa09/readings/Auer+al-UCB.pdf" rel="nofollow">UCB1 algorithm</a> 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. </p>

<p>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$? </p>

<p>Thank you!</p>

<lg.learning>
Stochastic multi-armed bandit problem with transition costs
angela o.
# Stochastic multi-armed bandit problem with transition costs

(Asked by: username_0 on 2011-01-14)

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](http://www.eecs.berkeley.edu/~pabbeel/cs287-fa09/readings/Auer+al-UCB.pdf) 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!

**Tags:** lg.learning

---

## 1 answers

### Answer by username_1 on 2011-01-14. Score: 6 | Accepted answer

Yes, it's been studied -- for example you can look at [this survey](http://gandalf.psych.umn.edu/groups/schraterlab/papers/A_Survey_On_MABSC.pdf), 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](http://jmlr.csail.mit.edu/papers/volume3/auer02a/auer02a.pdf).


---

