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(\sqrtKT \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(\sqrtNT\right). Our open problem is what can be achieved by asking M experts on every round, where 1 Cite this Paper BibTeX @InProceedings{pmlr-v30-Seldin13, title = {Open Problem: Adversarial Multiarmed Bandits with Limited Advice }, author = {Seldin, Yevgeny and Crammer, Koby and Bartlett, Peter}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {1067--1072}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Seldin13.pdf}, url = {https://proceedings.mlr.press/v30/Seldin13.html}, 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(\sqrtKT \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(\sqrtNT\right). Our open problem is what can be achieved by asking M experts on every round, where 1 Copy to Clipboard Download Endnote %0 Conference Paper %T Open Problem: Adversarial Multiarmed Bandits with Limited Advice %A Yevgeny Seldin %A Koby Crammer %A Peter Bartlett %B Proceedings of the 26th Annual Confere