Open Problem: Adversarial Multiarmed Bandits with Limited Advice

Yevgeny Seldin, Koby Crammer, Peter Bartlett
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:1067-1072, 2013.

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
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 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Seldin13 %I PMLR %P 1067--1072 %U https://proceedings.mlr.press/v30/Seldin13.html %V 30 %X 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
RIS
TY - CPAPER TI - Open Problem: Adversarial Multiarmed Bandits with Limited Advice AU - Yevgeny Seldin AU - Koby Crammer AU - Peter Bartlett BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Seldin13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 1067 EP - 1072 L1 - http://proceedings.mlr.press/v30/Seldin13.pdf UR - https://proceedings.mlr.press/v30/Seldin13.html AB - 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
APA
Seldin, Y., Crammer, K. & Bartlett, P.. (2013). Open Problem: Adversarial Multiarmed Bandits with Limited Advice . Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:1067-1072 Available from https://proceedings.mlr.press/v30/Seldin13.html.

Related Material