Open problem: Adversarial multiarmed bandits with limited advice

Yevgeny Seldin; Koby Crammer; Peter L. Bartlett

Open problem: Adversarial multiarmed bandits with limited advice

Yevgeny Seldin, Koby Crammer, Peter L. Bartlett

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(√KT ln N) 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(√NT). Our open problem is what can be achieved by asking M experts on every round, where 1 < M < N.

Original language	English
Title of host publication	JMLR Workshop and Conference Proceedings, 30 (COLT)
Publication date	2013
Publication status	Published - 2013
Externally published	Yes

Access to Document

http://jmlr.org/proceedings/papers/v30/Seldin13.pdf

Cite this

@inproceedings{fa7401edc58646cc91494e826122528c,

title = "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(√KT ln N) 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(√NT). Our open problem is what can be achieved by asking M experts on every round, where 1 < M < N.",

author = "Yevgeny Seldin and Koby Crammer and Bartlett, {Peter L.}",

year = "2013",

language = "English",

booktitle = "JMLR Workshop and Conference Proceedings, 30 (COLT)",

}

TY - GEN

T1 - Open problem: Adversarial multiarmed bandits with limited advice

AU - Seldin, Yevgeny

AU - Crammer, Koby

AU - Bartlett, Peter L.

PY - 2013

Y1 - 2013

N2 - 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(√KT ln N) 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(√NT). Our open problem is what can be achieved by asking M experts on every round, where 1 < M < N.

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(√KT ln N) 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(√NT). Our open problem is what can be achieved by asking M experts on every round, where 1 < M < N.

M3 - Article in proceedings

BT - JMLR Workshop and Conference Proceedings, 30 (COLT)

ER -