An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits

Peter Auer, Chao-Kai Chiang
29th Annual Conference on Learning Theory, PMLR 49:116-120, 2016.

Abstract

We present an algorithm that achieves almost optimal pseudo-regret bounds against adversarial and stochastic bandits. Against adversarial bandits the pseudo-regret is O(K\sqrtn \log n) and against stochastic bandits the pseudo-regret is O(\sum_i (\log n)/\Delta_i). We also show that no algorithm with O(\log n) pseudo-regret against stochastic bandits can achieve \tildeO(\sqrtn) expected regret against adaptive adversarial bandits. This complements previous results of Bubeck and Slivkins (2012) that show \tildeO(\sqrtn) expected adversarial regret with O((\log n)^2) stochastic pseudo-regret.

Cite this Paper

BibTeX
@InProceedings{pmlr-v49-auer16, title = {An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits}, author = {Auer, Peter and Chiang, Chao-Kai}, booktitle = {29th Annual Conference on Learning Theory}, pages = {116--120}, year = {2016}, editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad}, volume = {49}, series = {Proceedings of Machine Learning Research}, address = {Columbia University, New York, New York, USA}, month = {23--26 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v49/auer16.pdf}, url = {https://proceedings.mlr.press/v49/auer16.html}, abstract = {We present an algorithm that achieves almost optimal pseudo-regret bounds against adversarial and stochastic bandits. Against adversarial bandits the pseudo-regret is O(K\sqrtn \log n) and against stochastic bandits the pseudo-regret is O(\sum_i (\log n)/\Delta_i). We also show that no algorithm with O(\log n) pseudo-regret against stochastic bandits can achieve \tildeO(\sqrtn) expected regret against adaptive adversarial bandits. This complements previous results of Bubeck and Slivkins (2012) that show \tildeO(\sqrtn) expected adversarial regret with O((\log n)^2) stochastic pseudo-regret. } }
Endnote
%0 Conference Paper %T An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits %A Peter Auer %A Chao-Kai Chiang %B 29th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2016 %E Vitaly Feldman %E Alexander Rakhlin %E Ohad Shamir %F pmlr-v49-auer16 %I PMLR %P 116--120 %U https://proceedings.mlr.press/v49/auer16.html %V 49 %X We present an algorithm that achieves almost optimal pseudo-regret bounds against adversarial and stochastic bandits. Against adversarial bandits the pseudo-regret is O(K\sqrtn \log n) and against stochastic bandits the pseudo-regret is O(\sum_i (\log n)/\Delta_i). We also show that no algorithm with O(\log n) pseudo-regret against stochastic bandits can achieve \tildeO(\sqrtn) expected regret against adaptive adversarial bandits. This complements previous results of Bubeck and Slivkins (2012) that show \tildeO(\sqrtn) expected adversarial regret with O((\log n)^2) stochastic pseudo-regret.
RIS
TY - CPAPER TI - An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits AU - Peter Auer AU - Chao-Kai Chiang BT - 29th Annual Conference on Learning Theory DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-auer16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 49 SP - 116 EP - 120 L1 - http://proceedings.mlr.press/v49/auer16.pdf UR - https://proceedings.mlr.press/v49/auer16.html AB - We present an algorithm that achieves almost optimal pseudo-regret bounds against adversarial and stochastic bandits. Against adversarial bandits the pseudo-regret is O(K\sqrtn \log n) and against stochastic bandits the pseudo-regret is O(\sum_i (\log n)/\Delta_i). We also show that no algorithm with O(\log n) pseudo-regret against stochastic bandits can achieve \tildeO(\sqrtn) expected regret against adaptive adversarial bandits. This complements previous results of Bubeck and Slivkins (2012) that show \tildeO(\sqrtn) expected adversarial regret with O((\log n)^2) stochastic pseudo-regret. ER -
APA
Auer, P. & Chiang, C.. (2016). An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:116-120 Available from https://proceedings.mlr.press/v49/auer16.html.

Related Material