Evaluation and Analysis of the Performance of the EXP3 Algorithm in Stochastic Environments


Yevgeny Seldin, Csaba Szepesvári, Peter Auer, Yasin Abbasi-Yadkori ;
Proceedings of the Tenth European Workshop on Reinforcement Learning, PMLR 24:103-116, 2013.


EXP3 is a popular algorithm for adversarial multiarmed bandits, suggested and analyzed in this setting by Auer et al. [2002b]. Recently there was an increased interest in the performance of this algorithm in the stochastic setting, due to its new applications to stochastic multiarmed bandits with side information [Seldin et al., 2011] and to multiarmed bandits in the mixed stochastic-adversarial setting [Bubeck and Slivkins, 2012]. We present an empirical evaluation and improved analysis of the performance of the EXP3 algorithm in the stochastic setting, as well as a modification of the EXP3 algorithm capable of achieving “logarithmic” regret in stochastic environments.

Related Material