Decoupling Exploration and Exploitation in Multi-Armed Bandits
Abstract
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 √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.
Cite
Text
Avner et al. "Decoupling Exploration and Exploitation in Multi-Armed Bandits." International Conference on Machine Learning, 2012.Markdown
[Avner et al. "Decoupling Exploration and Exploitation in Multi-Armed Bandits." International Conference on Machine Learning, 2012.](https://mlanthology.org/icml/2012/avner2012icml-decoupling/)BibTeX
@inproceedings{avner2012icml-decoupling,
title = {{Decoupling Exploration and Exploitation in Multi-Armed Bandits}},
author = {Avner, Orly and Mannor, Shie and Shamir, Ohad},
booktitle = {International Conference on Machine Learning},
year = {2012},
url = {https://mlanthology.org/icml/2012/avner2012icml-decoupling/}
}