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 = {Peter Auer and Chao-Kai Chiang}, booktitle = {29th Annual Conference on Learning Theory}, pages = {116--120}, year = {2016}, editor = {Vitaly Feldman and Alexander Rakhlin and Ohad Shamir}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 116--120 %U http://proceedings.mlr.press %V 49 %W PMLR %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 PY - 2016/06/06 DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-auer16 PB - PMLR SP - 116 DP - PMLR EP - 120 L1 - http://proceedings.mlr.press/v49/auer16.pdf UR - http://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 PMLR 49:116-120

Related Material