Decoupling exploration and exploitation in multi-armed bandits. arXiv:1205.2874v1 [cs.LG

We consider a multi-armed bandit problem where the decision maker can explore and ex-ploit different arms at every round. The ex-ploited arm adds to the decision maker’s cu-mulative reward (without necessarily observ-ing the reward) while the explored arm re-veals its value. We devise algorithms for this setup and show that the dependence on the number of arms, k, can be much better than the standard k dependence, depending on the behavior of the arms ’ reward sequences. For the important case of piecewise station-ary stochastic bandits, we show a significant improvement over existing algorithms. Our algorithms are based on a non-uniform sam-pling policy, which we show is essential to the success of any algorithm in the adversarial setup. Finally, we show some simulation re-sults on an ultra-wide band channel selection inspired setting indicating the applicability of our algorithms. 1