We consider a sequential multi-task problem, where each task is modeled as the stochastic Multi-Armed Bandit with K arms. We assume the bandit tasks are adjacently similar in the sense that the difference between the mean rewards of the arms for any two consecutive tasks is bounded by