Decoupling Exploration and Exploitation in Multi-Armed Bandits
This addresses a fundamental problem in sequential decision-making for researchers and practitioners, offering incremental algorithmic advances.
The paper tackles the multi-armed bandit problem by decoupling exploration and exploitation, allowing separate actions each round, and shows that algorithms achieve better dependence on the number of arms than the standard square root of k, with significant improvement for piecewise stationary stochastic bandits.
We consider a multi-armed bandit problem where the decision maker can explore and exploit different arms at every round. The exploited arm adds to the decision maker's cumulative reward (without necessarily observing the reward) while the explored arm reveals 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 square root of k dependence, depending on the behavior of the arms' reward sequences. For the important case of piecewise stationary stochastic bandits, we show a significant improvement over existing algorithms. Our algorithms are based on a non-uniform sampling policy, which we show is essential to the success of any algorithm in the adversarial setup. Finally, we show some simulation results on an ultra-wide band channel selection inspired setting indicating the applicability of our algorithms.