On Context-Dependent Clustering of Bandits

Claudio Gentile, Shuai Li, Purushottam Kar, Alexandros Karatzoglou, Giovanni Zappella, Evans Etrue
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:1253-1262, 2017.

Abstract

We investigate a novel cluster-of-bandit algorithm CAB for collaborative recommendation tasks that implements the underlying feedback sharing mechanism by estimating user neighborhoods in a context-dependent manner. CAB makes sharp departures from the state of the art by incorporating collaborative effects into inference, as well as learning processes in a manner that seamlessly interleaves explore-exploit tradeoffs and collaborative steps. We prove regret bounds for CAB under various data-dependent assumptions which exhibit a crisp dependence on the expected number of clusters over the users, a natural measure of the statistical difficulty of the learning task. Experiments on production and real-world datasets show that CAB offers significantly increased prediction performance against a representative pool of state-of-the-art methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-gentile17a, title = {On Context-Dependent Clustering of Bandits}, author = {Claudio Gentile and Shuai Li and Purushottam Kar and Alexandros Karatzoglou and Giovanni Zappella and Evans Etrue}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {1253--1262}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/gentile17a/gentile17a.pdf}, url = {https://proceedings.mlr.press/v70/gentile17a.html}, abstract = {We investigate a novel cluster-of-bandit algorithm CAB for collaborative recommendation tasks that implements the underlying feedback sharing mechanism by estimating user neighborhoods in a context-dependent manner. CAB makes sharp departures from the state of the art by incorporating collaborative effects into inference, as well as learning processes in a manner that seamlessly interleaves explore-exploit tradeoffs and collaborative steps. We prove regret bounds for CAB under various data-dependent assumptions which exhibit a crisp dependence on the expected number of clusters over the users, a natural measure of the statistical difficulty of the learning task. Experiments on production and real-world datasets show that CAB offers significantly increased prediction performance against a representative pool of state-of-the-art methods.} }
Endnote
%0 Conference Paper %T On Context-Dependent Clustering of Bandits %A Claudio Gentile %A Shuai Li %A Purushottam Kar %A Alexandros Karatzoglou %A Giovanni Zappella %A Evans Etrue %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-gentile17a %I PMLR %P 1253--1262 %U https://proceedings.mlr.press/v70/gentile17a.html %V 70 %X We investigate a novel cluster-of-bandit algorithm CAB for collaborative recommendation tasks that implements the underlying feedback sharing mechanism by estimating user neighborhoods in a context-dependent manner. CAB makes sharp departures from the state of the art by incorporating collaborative effects into inference, as well as learning processes in a manner that seamlessly interleaves explore-exploit tradeoffs and collaborative steps. We prove regret bounds for CAB under various data-dependent assumptions which exhibit a crisp dependence on the expected number of clusters over the users, a natural measure of the statistical difficulty of the learning task. Experiments on production and real-world datasets show that CAB offers significantly increased prediction performance against a representative pool of state-of-the-art methods.
APA
Gentile, C., Li, S., Kar, P., Karatzoglou, A., Zappella, G. & Etrue, E.. (2017). On Context-Dependent Clustering of Bandits. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:1253-1262 Available from https://proceedings.mlr.press/v70/gentile17a.html.

Related Material