Bandits, Query Learning, and the Haystack Dimension

Kareem Amin, Michael Kearns, Umar Syed
Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:87-106, 2011.

Abstract

Motivated by multi-armed bandits (MAB) problems with a very large or even infinite number of arms, we consider the problem of finding a maximum of an unknown target function by querying the function at chosen inputs (or arms). We give an analysis of the query complexity of this problem, under the assumption that the payoff of each arm is given by a function belonging to a known, finite, but otherwise arbitrary function class. Our analysis centers on a new notion of function class complexity that we call the haystack dimension, which is used to prove the approximate optimality of a simple greedy algorithm. This algorithm is then used as a subroutine in a functional MAB algorithm, yielding provably near-optimal regret. We provide a generalization to the infinite cardinality setting, and comment on how our analysis is connected to, and improves upon, existing results for query learning and generalized binary search.

Cite this Paper

BibTeX
@InProceedings{pmlr-v19-amin11a, title = {Bandits, Query Learning, and the Haystack Dimension}, author = {Amin, Kareem and Kearns, Michael and Syed, Umar}, booktitle = {Proceedings of the 24th Annual Conference on Learning Theory}, pages = {87--106}, year = {2011}, editor = {Kakade, Sham M. and von Luxburg, Ulrike}, volume = {19}, series = {Proceedings of Machine Learning Research}, address = {Budapest, Hungary}, month = {09--11 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v19/amin11a/amin11a.pdf}, url = {https://proceedings.mlr.press/v19/amin11a.html}, abstract = {Motivated by multi-armed bandits (MAB) problems with a very large or even infinite number of arms, we consider the problem of finding a maximum of an unknown target function by querying the function at chosen inputs (or arms). We give an analysis of the query complexity of this problem, under the assumption that the payoff of each arm is given by a function belonging to a known, finite, but otherwise arbitrary function class. Our analysis centers on a new notion of function class complexity that we call the haystack dimension, which is used to prove the approximate optimality of a simple greedy algorithm. This algorithm is then used as a subroutine in a functional MAB algorithm, yielding provably near-optimal regret. We provide a generalization to the infinite cardinality setting, and comment on how our analysis is connected to, and improves upon, existing results for query learning and generalized binary search.} }
Endnote
%0 Conference Paper %T Bandits, Query Learning, and the Haystack Dimension %A Kareem Amin %A Michael Kearns %A Umar Syed %B Proceedings of the 24th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2011 %E Sham M. Kakade %E Ulrike von Luxburg %F pmlr-v19-amin11a %I PMLR %P 87--106 %U https://proceedings.mlr.press/v19/amin11a.html %V 19 %X Motivated by multi-armed bandits (MAB) problems with a very large or even infinite number of arms, we consider the problem of finding a maximum of an unknown target function by querying the function at chosen inputs (or arms). We give an analysis of the query complexity of this problem, under the assumption that the payoff of each arm is given by a function belonging to a known, finite, but otherwise arbitrary function class. Our analysis centers on a new notion of function class complexity that we call the haystack dimension, which is used to prove the approximate optimality of a simple greedy algorithm. This algorithm is then used as a subroutine in a functional MAB algorithm, yielding provably near-optimal regret. We provide a generalization to the infinite cardinality setting, and comment on how our analysis is connected to, and improves upon, existing results for query learning and generalized binary search.
RIS
TY - CPAPER TI - Bandits, Query Learning, and the Haystack Dimension AU - Kareem Amin AU - Michael Kearns AU - Umar Syed BT - Proceedings of the 24th Annual Conference on Learning Theory DA - 2011/12/21 ED - Sham M. Kakade ED - Ulrike von Luxburg ID - pmlr-v19-amin11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 19 SP - 87 EP - 106 L1 - http://proceedings.mlr.press/v19/amin11a/amin11a.pdf UR - https://proceedings.mlr.press/v19/amin11a.html AB - Motivated by multi-armed bandits (MAB) problems with a very large or even infinite number of arms, we consider the problem of finding a maximum of an unknown target function by querying the function at chosen inputs (or arms). We give an analysis of the query complexity of this problem, under the assumption that the payoff of each arm is given by a function belonging to a known, finite, but otherwise arbitrary function class. Our analysis centers on a new notion of function class complexity that we call the haystack dimension, which is used to prove the approximate optimality of a simple greedy algorithm. This algorithm is then used as a subroutine in a functional MAB algorithm, yielding provably near-optimal regret. We provide a generalization to the infinite cardinality setting, and comment on how our analysis is connected to, and improves upon, existing results for query learning and generalized binary search. ER -
APA
Amin, K., Kearns, M. & Syed, U.. (2011). Bandits, Query Learning, and the Haystack Dimension. Proceedings of the 24th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 19:87-106 Available from https://proceedings.mlr.press/v19/amin11a.html.

Related Material