Open Problem: Adversarial Multiarmed Bandits with Limited Advice
Abstract
Adversarial multiarmed bandits with expert advice is one of the fundamental problems in studying the exploration-exploitation trade-off. It is known that if we observe the advice of all experts on every round we can achieve O\left(\sqrt{KT} \ln N\right) regret, where K is the number of arms, T is the number of game rounds, and N is the number of experts. It is also known that if we observe the advice of just one expert on every round, we can achieve regret of order O\left(\sqrt{NT}\right). Our open problem is what can be achieved by asking M experts on every round, where 1<M<N.
Cite
Text
Seldin et al. "Open Problem: Adversarial Multiarmed Bandits with Limited Advice." Annual Conference on Computational Learning Theory, 2013.Markdown
[Seldin et al. "Open Problem: Adversarial Multiarmed Bandits with Limited Advice." Annual Conference on Computational Learning Theory, 2013.](https://mlanthology.org/colt/2013/seldin2013colt-open/)BibTeX
@inproceedings{seldin2013colt-open,
title = {{Open Problem: Adversarial Multiarmed Bandits with Limited Advice}},
author = {Seldin, Yevgeny and Crammer, Koby and Bartlett, Peter L.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2013},
pages = {1067-1072},
url = {https://mlanthology.org/colt/2013/seldin2013colt-open/}
}