Boosting with Online Binary Learners for the Multiclass Bandit Problem

Shang-Tse Chen, Hsuan-Tien Lin, Chi-Jen Lu
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):342-350, 2014.

Abstract

We consider the problem of online multiclass prediction in the bandit setting. Compared with the full-information setting, in which the learner can receive the true label as feedback after making each prediction, the bandit setting assumes that the learner can only know the correctness of the predicted label. Because the bandit setting is more restricted, it is difficult to design good bandit learners and currently there are not many bandit learners. In this paper, we propose an approach that systematically converts existing online binary classifiers to promising bandit learners with strong theoretical guarantee. The approach matches the idea of boosting, which has been shown to be powerful for batch learning as well as online learning. In particular, we establish the weak-learning condition on the online binary classifiers, and show that the condition allows automatically constructing a bandit learner with arbitrary strength by combining several of those classifiers. Experimental results on several real-world data sets demonstrate the effectiveness of the proposed approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-chenb14, title = {Boosting with Online Binary Learners for the Multiclass Bandit Problem}, author = {Chen, Shang-Tse and Lin, Hsuan-Tien and Lu, Chi-Jen}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {342--350}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/chenb14.pdf}, url = {https://proceedings.mlr.press/v32/chenb14.html}, abstract = {We consider the problem of online multiclass prediction in the bandit setting. Compared with the full-information setting, in which the learner can receive the true label as feedback after making each prediction, the bandit setting assumes that the learner can only know the correctness of the predicted label. Because the bandit setting is more restricted, it is difficult to design good bandit learners and currently there are not many bandit learners. In this paper, we propose an approach that systematically converts existing online binary classifiers to promising bandit learners with strong theoretical guarantee. The approach matches the idea of boosting, which has been shown to be powerful for batch learning as well as online learning. In particular, we establish the weak-learning condition on the online binary classifiers, and show that the condition allows automatically constructing a bandit learner with arbitrary strength by combining several of those classifiers. Experimental results on several real-world data sets demonstrate the effectiveness of the proposed approach.} }
Endnote
%0 Conference Paper %T Boosting with Online Binary Learners for the Multiclass Bandit Problem %A Shang-Tse Chen %A Hsuan-Tien Lin %A Chi-Jen Lu %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-chenb14 %I PMLR %P 342--350 %U https://proceedings.mlr.press/v32/chenb14.html %V 32 %N 1 %X We consider the problem of online multiclass prediction in the bandit setting. Compared with the full-information setting, in which the learner can receive the true label as feedback after making each prediction, the bandit setting assumes that the learner can only know the correctness of the predicted label. Because the bandit setting is more restricted, it is difficult to design good bandit learners and currently there are not many bandit learners. In this paper, we propose an approach that systematically converts existing online binary classifiers to promising bandit learners with strong theoretical guarantee. The approach matches the idea of boosting, which has been shown to be powerful for batch learning as well as online learning. In particular, we establish the weak-learning condition on the online binary classifiers, and show that the condition allows automatically constructing a bandit learner with arbitrary strength by combining several of those classifiers. Experimental results on several real-world data sets demonstrate the effectiveness of the proposed approach.
RIS
TY - CPAPER TI - Boosting with Online Binary Learners for the Multiclass Bandit Problem AU - Shang-Tse Chen AU - Hsuan-Tien Lin AU - Chi-Jen Lu BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-chenb14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 1 SP - 342 EP - 350 L1 - http://proceedings.mlr.press/v32/chenb14.pdf UR - https://proceedings.mlr.press/v32/chenb14.html AB - We consider the problem of online multiclass prediction in the bandit setting. Compared with the full-information setting, in which the learner can receive the true label as feedback after making each prediction, the bandit setting assumes that the learner can only know the correctness of the predicted label. Because the bandit setting is more restricted, it is difficult to design good bandit learners and currently there are not many bandit learners. In this paper, we propose an approach that systematically converts existing online binary classifiers to promising bandit learners with strong theoretical guarantee. The approach matches the idea of boosting, which has been shown to be powerful for batch learning as well as online learning. In particular, we establish the weak-learning condition on the online binary classifiers, and show that the condition allows automatically constructing a bandit learner with arbitrary strength by combining several of those classifiers. Experimental results on several real-world data sets demonstrate the effectiveness of the proposed approach. ER -
APA
Chen, S., Lin, H. & Lu, C.. (2014). Boosting with Online Binary Learners for the Multiclass Bandit Problem. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(1):342-350 Available from https://proceedings.mlr.press/v32/chenb14.html.

Related Material